Pagini recente » Cod sursa (job #2752394) | Cod sursa (job #2361112) | Cod sursa (job #2088919) | Cod sursa (job #412216) | Cod sursa (job #1997571)
#include <iostream>
#include <fstream>
#include <cstring>
#include <list>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char N[2000003],M[2000003];
int n,m,P[2000003];
int nrpoz;
list<int>poz;
void Prefix()
{
int i = 0,j = 1;
while( j < n )
{
if( N[i] == N[j] )
{
P[j] = i+1;
i++;
j++;
}
else
{
if( i == 0 )
{
P[j] = 0;
j++;
}
else
{
i = P[i-1];
}
}
}
}
void KMP()
{
int i = 0,j = 0;
while( j < m )
{
if( N[i] == M[j] )
{
i++;
j++;
if( i == n )
{
nrpoz++;
if( nrpoz < 1001 )
poz.push_back(j-n);
i = P[i-1];
}
}
else
{
if( i == 0 )
{
j++;
}
else
{
i = P[i];
}
}
}
}
int main()
{
f>>N>>M;
n = strlen(N);
m = strlen(M);
Prefix();
KMP();
g<<nrpoz<<'\n';
for(list<int>::iterator it = poz.begin() ; it != poz.end() ; it++)
g<<*it<<' ';
return 0;
}