Pagini recente » Cod sursa (job #106705) | Cod sursa (job #1613846) | Cod sursa (job #2864907) | Cod sursa (job #2531290) | Cod sursa (job #2412044)
#include<bits/stdc++.h>
using namespace std;
const int maxN=(2e6)+5;
char s[maxN],p[maxN];
int pref[maxN];
vector<int> sol;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",s+1);
scanf("\n");
scanf("%s",p+1);
int k=0;
int n=strlen(s+1);
int m=strlen(p+1);
for(int i=2;i<=n;i++)
{
while(k && s[k+1]!=s[i]) k=pref[k];
if(s[k+1]==s[i]) k++;
pref[i]=k;
}
k=0;
int sz=0;
for(int i=1;i<=m;i++)
{
while(k && s[k+1]!=p[i]) k=pref[k];
if(s[k+1]==p[i]) k++;
if(k>=n)
{
sz++;
if(sz<=1000) sol.push_back(i-n);
}
}
printf("%d\n",sz);
for(auto it:sol)
printf("%d ",it);
printf("\n");
return 0;
}