Pagini recente » Cod sursa (job #1362925) | Cod sursa (job #57857) | Cod sursa (job #2419282) | Cod sursa (job #899525) | Cod sursa (job #2365281)
#include<bits/stdc++.h>
using namespace std;
const int maxN=2000005;
vector<int> matches;
char P[maxN],S[maxN];
int pref[maxN];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",P+1);
scanf("\n");
scanf("%s",S+1);
int n=strlen(P+1);
int m=strlen(S+1);
int k=0;
pref[1]=0;
for(int i=2;i<=n;i++)
{
while(k>0 && P[k+1]!=P[i]) k=pref[k];
if(P[k+1]==P[i]) k++;
pref[i]=k;
}
k=0;
for(int i=1;i<=m;i++)
{
while(k>0 && P[k+1]!=S[i]) k=pref[k];
if(P[k+1]==S[i]) k++;
if(k==n && (int)matches.size()<1000) matches.push_back(i-n);
}
//sort(matches.begin(),matches.end());
printf("%d\n",(int)matches.size());
for(auto it:matches) printf("%d ",it);
printf("\n");
return 0;
}