Pagini recente » Cod sursa (job #1410475) | Cod sursa (job #887977) | Cod sursa (job #62769) | Cod sursa (job #2230920) | Cod sursa (job #2750067)
#include <iostream>
#include <fstream>
#include <cstring>
#define Nmax 2000006
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char x[Nmax],y[Nmax];
int pi[Nmax],val[1050];
int minim(int a,int b)
{
if(a>b) return b;
return a;
}
void asezare(int n, char s[])
{
int i;
for(i=n;i>0;i--)
s[i]=s[i-1];
s[n+1]=0;
}
void construire()
{
int n,k,i;
n=strlen(x);
k=0;
pi[1]=0;
for(i=2;i<=n;i++)
{
while(k>0&&(x[i]!=x[k+1]))
k=pi[k];
if(x[k+1]==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);
asezare(n,x);
asezare(m,y);
construire();
k=0;
for(i=1;i<=m;i++)
{
while(k>0&&(y[i]!=x[k+1]))
k=pi[k];
if(y[i]==x[k+1])
k++;
if(k==n)
{
k=pi[n];
++z;
if(n<=1000)
val[z]=i-n;
}
}
g<<z<<'\n';
for(i=1;i<=minim(z,1000);i++)
g<<val[i]<<" ";
return 0;
}