Pagini recente » Cod sursa (job #1705241) | Cod sursa (job #978969) | Cod sursa (job #949213) | Cod sursa (job #1442759) | Cod sursa (job #996204)
Cod sursa(job #996204)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int Lmax = 2000002;
int L[Lmax];
char Pattern[Lmax], Text[Lmax];
vector <int> match;
int P, T;
void read()
{
ifstream f("strmatch.in");
f >> ( Pattern + 1 );
f >> ( Text + 1 );
Pattern[0] = ' ';
Text[0] = ' ';
P = strlen ( Pattern ) - 1;
T = strlen ( Text ) - 1;
f.close();
}
void prefix()
{
L[1] = 0;
int k = 0;
for ( int i = 2; i <= P; ++i )
{
while ( k && Pattern[k + 1] != Pattern[i] )
k = L[k];
if ( Pattern[k + 1] == Pattern[i] )
k++;
L[i] = k;
}
}
void KMP()
{
int k = 0;
for ( int i = 1; i <= T; ++i )
{
while ( k && Pattern[k + 1] != Text[i] )
k = L[k];
if ( Pattern[k + 1] == Text[i] )
k++;
if ( k == P )
{
match.push_back( i - P );
k = L[k];
}
}
}
void print()
{
ofstream g("strmatch.out");
g << match.size() << "\n";
for ( unsigned i = 0; i < min( match.size(), (unsigned)1000 ); ++i )
g << match[i] << " ";
g << "\n";
g.close();
}
int main()
{
read();
prefix();
KMP();
print();
return 0;
}