Pagini recente » Cod sursa (job #2236821) | Cod sursa (job #3120833) | Cod sursa (job #1540206) | Cod sursa (job #1766736) | Cod sursa (job #2293776)
#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;
scanf("%s", &s);
n=strlen(s);
strcpy(s+1,s);
nn=n;
scanf("%s", &ss);
strcpy(s+n+2, ss);
s[n+1]='#';
n=strlen(s);
l=r=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=2; i<n && sol.size()<1000; i++)
if(z[i]==nn)
sol.push_back(i);
printf("%d\n", sol.size());
for(i=0; i<sol.size(); i++)
printf("%d ", sol[i]-nn-2);
return 0;
}