Pagini recente » Cod sursa (job #385013) | Cod sursa (job #597910) | Cod sursa (job #1785726) | Cod sursa (job #848017) | Cod sursa (job #1004637)
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
char A[2000005];
char B[2000005];
int pi[2000005];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int n,m;
gets(A+1);n=strlen(A+1);
gets(B+1);m=strlen(B+1);
pi[1]=0;int k=0;
for(int i=2;i<=n;i++)
{
while(k>0 && A[k+1]!=A[i])
k=pi[k];
if(A[k+1]==A[i]) k++;
pi[i]=k;
}
vector<int> sol;
k=0;
for(int i=1;i<=m;i++)
{
while(k>0 && A[k+1]!=B[i])
k=pi[k];
if(A[k+1]==B[i])
k++;
if(k==n)
sol.push_back(i-k);
}
printf("%d\n",(int)sol.size());
for(int i=0;i<min(1000,(int)sol.size());i++)
printf("%d%c",sol[i],i==min(1000,(int)sol.size())-1?'\n':' ');
return 0;
}