Pagini recente » Cod sursa (job #2933755) | Cod sursa (job #1748539) | Cod sursa (job #13325) | Cod sursa (job #1961024) | Cod sursa (job #2293818)
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
char s[4000005];
char ss[2000005];
int z[4000005];
vector <int> sol;
int main()
{ freopen("strmatch.in", "r",stdin);
freopen("strmatch.out", "w",stdout);
int n,nn,l,r,i;
char c;
c=fgetc(stdin);
for(i=1; c!='\n'; c=fgetc(stdin),i++)
s[i]=c;
nn=i-1;
s[i]='#';
c=fgetc(stdin);
for(++i; c!='\n' && c!=EOF; c=fgetc(stdin),i++)
s[i]=c;
n=i-1;
l=r=0;
s[0]=0;
for(i=2; i<=n; i++){
if(r>=i)
z[i]=min(z[i-l+1], r-i+1);
for(; i+z[i]<=n && s[z[i]+1]==s[i+z[i]]; z[i]++);
if(r<z[i]+i-1){
r=z[i]+i-1;
l=i;
}
}
for(i=nn+2; i<=n; i++)
if(z[i]>=nn)
sol.push_back(i);
printf("%d\n", sol.size());
for(i=0; i<=1000 && i<sol.size(); i++)
printf("%d ", sol[i]-nn-2);
return 0;
}