- #include<stdio.h>
- #define maxsize 100
- typedef struct string
- {
- int n;
- char s[maxsize];
- }string;
- int get_nextval(string &T,int nextval[])
- {
- int i=1;
- int j=0;
- nextval[1]=0;
- while(i<T.n)
- {
- if(j==0||T.s[i]==T.s[j])
- {
- ++i;
- ++j;
- nextval[i]=j;
- }
- else
- j=nextval[j];
- }
- return 0;
- }
- int Index(string &S,string &T,int pos)
- {
- int i=pos;
- int j=1;
- int nextval[255];
- get_nextval(T,nextval);
- while(i<=S.n&&j<=T.n)
- {
- if(j==0||S.s[i]==T.s[j])
- {
- ++i;
- ++j;
- }
- else
- j=nextval[j];
- }
- if(j>T.n)
- return i-T.n;
- else
- return 0;
- }
- int main()
- {
- string S,T;
- char c;
- int i=1,m;
- printf("请输入原字符串S,以#号结尾");
- while((c=getchar())!='#')
- {
- S.s[i]=c;
- i++;
- }
- S.n=i-1;
- printf("请输入检测字符串T,以#号结尾");
- fflush(stdin);
- i=1;
- while((c=getchar())!='#')
- {
- T.s[i]=c;
- i++;
- }
- T.n=i-1;
- m=Index(S,T,1);
- printf("检测结果为:");
- if(m==0)
- printf("找不到字符串!");
- else
- printf("找到字符串,从S的第%d个位置开始\n",m);
- return 0;
- }
来源: http://www.phpxs.com/code/1004102/