Pagini recente » Cod sursa (job #2698279) | Cod sursa (job #1989352) | Cod sursa (job #215923) | Cod sursa (job #649654) | Cod sursa (job #2746096)
#include <iostream>
#include <fstream>
#include <cstring>
#define minim(a, b) ((a < b) ? a : b)
#define Nmax 2000004
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char x[Nmax],y[Nmax];
int pi[Nmax],val[1050];
void construire()
{
int n,k,i;
n=strlen(x);
k=0;
pi[0]=0;
for(i=2;i<n;i++)
{
while(k>0&&(x[i]!=x[k+1]))
k=pi[k];
if(x[k]==x[i])
k++;
pi[i]=k;
}
}
int n,m,z=0,k,i;
int main()
{
f.getline(x,Nmax);
f.getline(y,Nmax);
m=strlen(y);
n=strlen(x);
construire();
k=0;
for(i=0;i<m;i++)
{
while(k>0&&(y[i]!=x[k+1]))
k=pi[k];
if(y[i]==x[k+1])
k++;
if(k==n-1)
{
k=pi[n];
++z;
val[z]=i-n+1;
}
}
g<<z<<'\n';
for(i=1;i<=z;i++)
g<<val[i]<<" ";
return 0;
}