Pagini recente » Monitorul de evaluare | Statistici Slayer (metal_master) | Cod sursa (job #1032964) | Istoria paginii utilizator/pleto | Cod sursa (job #1997592)
#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,j;
for( i = 0 , j = 1 ; j < n ; j++ )
{
while( i > 0 && N[i] != N[j] )
i = P[i-1];
if( N[i] == N[j] )
i++;
P[j] = i;
}
}
void KMP()
{
int i,j;
for( i = 0 , j = 0 ; j < m ; j++ )
{
while( i > 0 && N[i] != M[j] )
i = P[i-1];
if( N[i] == M[j] )
i++;
if( i == n )
if( ++nrpoz < 1001 )
poz.push_back(j-n+1);
}
}
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;
}