Pagini recente » Cod sursa (job #2304872) | Cod sursa (job #2830279) | Cod sursa (job #1288199) | Cod sursa (job #1789520) | Cod sursa (job #380839)
Cod sursa(job #380839)
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define nmax 2000002
#define mmax 2000002
int urm[mmax];
char t[nmax], p[mmax];
int d=0;
vector<int> v;
int n,m;
void urmator()
{
int k=-1,x;
urm[0]=0;
for(x=1;x<m;x++)
{
while(k>0&&p[k+1]!=p[x])
k=urm[k];
if(p[k+1]==p[x])
k++;
urm[x]=k;
}
}
int main()
{
int i, x=-1;
freopen("kmp.in", "r", stdin);
freopen("kmp.out", "w", stdout);
scanf("%s %s", &t, &p);
n=strlen(t); m=strlen(p);
urmator();
for(i=0;i<n;i++)
{
while(x>0&&p[x+1]!=t[i])
x=urm[x];
if(p[x+1]==t[i])
x++;
if(x==m-1)
{
x=urm[x];
d++;
v.push_back(i);
}
}
printf("%d\n", d);
for(i=1;i<=d;i++)
printf("%d ", v[i-1]);
return 0;
}