String Matching

Input

The input consists of several test cases. Each test case consists of two lines, first a non-empty pattern, then a non-empty text. Input is terminated by end-of-file. The input file will not be larger than 5 Mb.

Output

For each test case, output one line containing the positions of all the occurences of pattern in text, from first to last, separated by a single space.

Sample Input 1	Sample Output 1
pPopupheloHello there!peek a booyou speek a bootiful languageanasbananananaspaj	2 457

题意

多组输入，每组两行，模式串和对比串，输出上面的模式串在下面的字符串中的所有位置下标，下标从0开始

思路1

KMP算法，套个模版就可以了

思路2

用string的find，str2.find(str1,x)，关于这个函数的用法

代码1

#include
      
       #include
       
        using namespace std;int const MAXM = 4000000;char s[MAXM], t[MAXM];int next[MAXM], n;int shuchu[MAXM];void get_next(){    next[0] = -1;    int i = 0, j = -1;    while (t[i] != '\0')    {        if (j == -1 || t[i] == t[j])        {            i++;            j++;            next[i] = j;        }        else            j = next[j];    }}int KMP(){    get_next();    int i = 0, j = 0, ans = 0, len = strlen(t);    while (s[i])    {        if (j == -1 || s[i] == t[j])        {            i++;            j++;        }        else            j = next[j];        if (j == len)        {            j = next[j];            shuchu[ans++] = i;        }    }    return ans;}int main(){        while (gets(t)) {        gets(s);        int ss = KMP();        for (int i = 0; i < ss; i++)        {            if (i)printf(" ");            printf("%d", shuchu[i]-strlen(t));        }        puts("");    }}
       
      

代码2

#include
      
       using namespace std;int main(){    string str1,str2;    int cnt[100000];    while(getline(cin,str1)){        getline(cin,str2);        int pos=0,x=0;        while(str2.find(str1,x)!=-1&&x