|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
利用一个next数组存储匹配串每一个位置的回溯下标,当用匹配串与被匹配串进行逐个比较时,若出现匹配错误,可以利用next数组快速回溯。
next数组:当前缀和后缀一致时,记录一次下标;若不一致,固定后缀,回溯前缀直至最开始的下标0,记录下标1,表示需要从头开始匹配。利用next数组我们可以快速地根据匹配串中重复的部分减少匹配次数。
- #include<cstdio>
- #include<cstdlib>
- #include<string>
- #include<iostream>
- using namespace std;
- void GetNext(char T[], int next[])
- {
- int i=1, j=0;
- next[1] = 0;
- while (i < T[0])
- {
- if (0 == j || T[i] == T[j])
- {
- i++;
- j++;
- if (T[i] == T[j])
- {
- next[i] = next[j];
- }
- else
- {
- next[i] = j;
- }
- }
- else
- {
- j = next[j];
- }
- }
- }
- void GetString(char str[])
- {
- int i;
- char temp;
- scanf_s("%c", &temp);
- for (i = 1; temp != ' '&&temp != '\n'; i++)
- {
- str[i] = temp;
- scanf_s("%c", &temp);
- }
- str[0] = i - 1 ;
- }
- int KMP(char S[], char T[],int next[])
- {
- int i=1,j=1;
- int flag = 0;
- while (i <= S[0] )
- {
- if (j==0||S[i] == T[j])
- {
- i++;
- j++;
- }
- else
- {
- j = next[j];
- }
- if (j > T[0] )
- {
- flag = 1;
- break;
- }
- }
- if (flag)return i;
- else return 0;
- }
- int main()
- {
- char S[256], T[256] ;
- int next[256];
- cout << "输入主串:";
- GetString(S);
- cout << "输入子串:";
- GetString(T);
- GetNext(T, next);
- int pos = KMP(S, T, next)-T[0];
- if (pos)cout << "YES,in the no." << pos << endl;
- else cout << "NO"<< endl;
- system("PAUSE");
- }
复制代码 |
评分
-
查看全部评分
|