数据结构实验之串一：KMP简单应用

数据结构实验之串一：KMP简单应用

Time Limit: 1000MS Memory limit: 65536K

题目描述

给定两个字符串string1和string2，判断string2是否为string1的子串。

输入

 输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。

输出

 对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。

示例输入

abc
a
123456
45
abc
ddd

示例输出

1
4
-1

#include<bits/stdc++.h>  
using namespace std;  
int next[1000001];  
int len1,len2;  
char string1[1000001],string2[1000001]; 
void kmp(int x,int y)  
{  
    int i=0,j=0;  //初始化，从头开始便利
    while(i<x&&j<y)  //遍历完主串或模式串跳出循环
    {  
        if(j==-1||string1[i]==string2[j])  
        {  
            i++;
            j++;  
        }  
        else  
            j=next[j];  
    }  
    if(j>=y)  
        printf("%d\n",i-j+1);  
    else  
        printf("-1\n");  
}  
void get_next(int len)  
{  
    int i=0;next[0]=-1;int j=-1;//在字符串中第一个字符没有前缀，因此赋予初值-1，（当然如果你是从零开始输入的赋值为0）  
    //这样得到第二个字符的next值就是0，因为第二个字符也只能回溯到0.  
    while(i<len)  
    {  
        if(j==-1||string2[i]==string2[j])  
        {  
            i++;j++;next[i]=j;//这里就是找前缀和后缀字符串长度的最大值，当比较不相等时，就回溯到这个下标的下一个再接着进行比较。  
        }  
        else  
            j=next[j];//如果不相等就回溯的string【j】的位置再接着进行比较。  
    }  
}    
int main()  
{  
    while(~scanf("%s%s",string1,string2))  
    {  
        len1=strlen(string1); // 存放主串的长度
        len2=strlen(string2);  //存放模式串长度
        get_next(len2-1);  
        kmp(len1,len2);  
    }  
}