Pagini recente » Cod sursa (job #2930044) | Cod sursa (job #668380) | Cod sursa (job #172136) | Cod sursa (job #220053) | Cod sursa (job #1076698)
#include <fstream>
#include <cstring>
using namespace std;
#define Nmax 2000001
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[Nmax],B[Nmax];
int m,n,pr;
int P[Nmax];
int nr,sol[1002];
void pref(int x)
{
int i,k=-1;
for(i=1;i<x;i++)
{
while(k>0 && A[k+1]!=A[i]) k=P[k];
if(A[i]==A[k+1]) k++;
P[i]=k;
}
}
void smatch()
{
int i,x=-1;
for(i=0;i<n;i++)
{
while(x>0 && A[x+1]!=B[i]) x=P[x];
if(A[x+1]==B[i]) x++;
if(x==m-1)
{
nr++;
if(nr<=1000) sol[nr]=i-m+1;
x=P[x];
}
}
}
int main()
{
int i;
f>>A>>B;
m=strlen(A);
n=strlen(B);
pref(m);
smatch();
if(nr<=1000)
{
g<<nr<<"\n";
for(i=1;i<=nr;i++) g<<sol[i]<<" ";
}
else
{ g<<1000<<"\n";
for(i=1;i<=1000;i++) g<<sol[i]<<" ";
}
g<<"\n";
f.close();
g.close();
return 0;
}