Pagini recente » Cod sursa (job #2395919) | Cod sursa (job #3240269) | Cod sursa (job #1358504) | Cod sursa (job #277306) | Cod sursa (job #1399555)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
char s[2000005],t[2000005];
int p[2000005],n;
vector<int>sol;
void prefix()
{
int k=0,i;
n=strlen(s+1);
for(i=2;i<=n;i++)
{
while(k&&s[k+1]!=s[i])k=p[k];
if(s[i]==s[k+1])
k++;
p[i]=k;
}
}
void kmp()
{
int k=0,m=strlen(t+1),i;
for(i=1;i<=m;i++)
{
while(k&&s[k+1]!=t[i])k=p[k];
if(t[i]==s[k+1])
k++;
if(k==n)
sol.pb(i-n);
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",s+1,t+1);
prefix();
kmp();
printf("%d\n",sol.size());
for(auto it:sol)
printf("%d ",it);
return 0;
}