Pagini recente » Cod sursa (job #2605826) | Cod sursa (job #3239514) | Cod sursa (job #1352803) | Cod sursa (job #2314491) | Cod sursa (job #2730707)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ( "strmatch.in" );
ofstream g ( "strmatch.out" );
const int NMAX = 2000002;
char A[NMAX], B[NMAX];
int m, n, p[NMAX], sol[1001], nr;
void prefix()
{
int k = 0;
p[1] = 0;
for ( int i = 2; i <= m; i++ )
{
while ( k > 0 && A[i] != A[k + 1] )
k = p[k];
if ( A[i] == A[k + 1] )
k++;
p[i] = k;
}
}
void KMP()
{
int k = 0;
for ( int i = 1; i <= n; i++ )
{
while ( k > 0 && A[k + 1] != B[i] )
k = p[k];
if ( A[k + 1] == B[i] )
k++;
if ( k == m )
{
nr++;
if ( nr <= 1000 )
sol[nr] = i - m;
k = p[k];
}
}
}
int main()
{
f.getline ( A + 1, NMAX );
m = f.gcount() - 1;
f.getline ( B + 1, NMAX );
n = f.gcount() - 1;
prefix();
KMP();
g << nr << '\n';
if ( nr >= 1000 )
nr = 1000;
for ( int i = 1; i <= nr; i++ )
g << sol[i] << ' ';
return 0;
}