Pagini recente » Cod sursa (job #950552) | Cod sursa (job #1279742) | Cod sursa (job #371937) | Cod sursa (job #2097620) | Cod sursa (job #1830937)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
char a[2000002],b[2000002];
int p[2000002],n,m;
int strlen(char *s)
{
int i;
for(i=0;s[i]!='\0';i++);
return i;
}
void sir_prefixe()
{
int i=2,j=1;
while(i<=n)
{
if(a[i]==a[j])
{
p[i]=j;
i++;
j++;
}
else
{
if(j>1)
j=p[j-1]+1;
else
{
p[i]=0;
i++;
j=1;
}
}
}
/* for(int i=1;i<=n;i++)
cout<<p[i]<<' '; */
}
void kmp()
{
vector<int>q;
for(int i=1,j=0;i<=m;i++)
{
while(j>0 && b[i]!=a[j+1])
j=p[j];
if(b[i]==a[j+1])
j++;
if(j==n)
{
q.push_back(i-n);
}
}
int k = q.size();
printf("%d\n",k);
for(int i=0;i<k;i++)
printf("%d ",q[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdin);
scanf("%s %s",a+1,b+1);
n=strlen(a+1);
m=strlen(b+1);
sir_prefixe();
kmp();
return 0;
}