Pagini recente » Istoria paginii utilizator/bizarr3 | Cod sursa (job #1588946) | Cod sursa (job #1409554) | Cod sursa (job #2839085) | Cod sursa (job #1656769)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int Nmax=2000005;
int na, P[Nmax], nb, nr, Rez[1000];
char A[Nmax], B[Nmax];
void pref()
{
int p=0;
for(int i=2;i<=na;i++)
{
while(p&&A[p+1]!=A[i])
p=P[p];
if(A[p+1]==A[i])
p++;
P[i]=p;
}
}
int main()
{
char c;
na=nb=0;
c=fin.get();
while(c!='\n')
{
na++;
A[na]=c;
c=fin.get();
}
c=fin.get();
while(c!='\n')
{
nb++;
B[nb]=c;
c=fin.get();
}
pref();
int p=0;
for(int i=1;i<=nb;i++)
{
while(p&&A[p+1]!=B[i])
p=P[p];
if(A[p+1]==B[i])
p++;
if(p==na&&nr<1000)
{
nr++;
Rez[nr]=i-na;
}
}
fout<<nr<<'\n';
for(int i=1;i<=nr;i++)
fout<<Rez[i]<<" ";
fout<<'\n';
return 0;
}