Pagini recente » Cod sursa (job #2145418) | Cod sursa (job #666491) | Cod sursa (job #1083214) | Cod sursa (job #2869375) | Cod sursa (job #2122871)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in" );
ofstream g("strmatch.out");
int state[2000004], prefix[2000004];
char A[2000004], B[2000004];
void InitializareAutomat(char A[])
{
int m = strlen(A+1);
prefix[1] = 0;
int i = 0;
for ( int j=2; j<=m; j++ )
{
while ( i>0 && A[i+1] != A[j] )
i = prefix[i];
if ( A[i+1] == A[j] ) i++;
prefix[j] = i;
}
}
void KMP(char A[], char B[])
{
int m = strlen(A+1);
int n = strlen(B+1);
for ( int i=1; i<=n; i++ )
if ( B[i] == A[state[i-1]+1] )
state[i] = state[i-1]+1;
else
{
int k = prefix[state[i-1]];
while ( k>0 && B[i] != A[k+1] ) k = prefix[k];
state[i] = k+1;
}
}
int out = 0;
vector<int> output;
void KMP_YT(char P[], char T[])
{
int n = strlen(T+1);
int m = strlen(P+1);
int i = 1;
int j = 1;
int k = 1;
while ( n-k >= m )
{
while ( j<=m && T[i] == P[j] ) {
i++;
j++;
}
if ( j > m ) {
out++;
output.push_back(k);
}
if ( prefix[j-1] > 0 )
k = i-prefix[j-1];
else {
if ( i == k ) i++;
k = i;
}
if ( j > 1 ) j = prefix[j-1] + 1;
}
}
int main()
{
f.getline(A+1, 2000004);
f.getline(B+1, 2000004);
int m = strlen(A+1);
int n = strlen(B+1);
InitializareAutomat(A);
KMP_YT(A, B);
g << out << '\n';
for ( int i=0; i<min(unsigned(1000), output.size()); i++ )
g << output[i] << ' ';
}