Pagini recente » Cod sursa (job #1603830) | Cod sursa (job #29748) | Cod sursa (job #1297118) | Cod sursa (job #2604337) | Cod sursa (job #2675233)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char pattern[2000000], text[2000000],*p;
int lps[2000000],len,n,nr,v[2000000];
void LPS()
{
n=strlen(pattern);
lps[0]=0;
int i=1;
while(i<n)
{
if(pattern[i]==pattern[len])
{
len++;
lps[i]=len;
i++;
}
else
if(len!=0)
len=lps[len-1];
else
lps[i++]=0;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", &pattern, &text);
int i=0,j=0;
int m=strlen(text);
LPS();
while(i<m)
{
if(text[i]==pattern[j])
i++,j++;
else
if(j!=0)
j=lps[j-1];
else
i++;
if(j==n)
{
v[nr++]=i-j;
j=lps[j-1];
}
}
printf("%d\n", nr);
for(int i=0;i<nr;++i)
printf("%d ", v[i]);
return 0;
}