Pagini recente » Cod sursa (job #1234988) | Cod sursa (job #1485600) | Cod sursa (job #1655424) | Cod sursa (job #2626738) | Cod sursa (job #2365162)
#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 && 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 && P[k+1]!=S[i]) k=pref[k];
if(P[k+1]==S[i]) k++;
if(k==n) matches.push_back(i-n);
}
sort(matches.begin(),matches.end());
printf("%d\n",min(1000,(int)matches.size()));
if((int)matches.size()>1000) matches.resize(1000);
for(auto it:matches)
printf("%d ",it);
return 0;
}