Pagini recente » Rating Daniela Carbunaru (abramburica) | Cod sursa (job #1405484) | Cod sursa (job #689831) | Cod sursa (job #130254) | Cod sursa (job #348481)
Cod sursa(job #348481)
#include <iostream>
#include <fstream>
using namespace std;
#define fin "strmatch.in"
#define fout "strmatch.out"
#define NMAX 2000100
char a[NMAX], b[NMAX];
int pi[NMAX];
void prefix(char a[], int pi[])
{
int i, pos;
pi[ 1 ] = 0;
pos = 0;
for ( i = 2; a[i]; ++i )
{
while ( pos > 0 && a[pos+1] != a[i] )
pos = pi[pos];
if ( a[pos+1] == a[i] )
++pos;
pi[i] = pos;
}
}
int kmp(char model[], char str[], int pif[])
{
int i, pos, ret = 0;
pos = 0;
for ( i = 1; str[i]; ++i )
{
while ( pos > 0 && model[ pos + 1 ] != str[i] )
pos = pif[pos];
if ( model[ pos + 1 ] == str[i] )
++pos;
if ( model[ pos + 1 ] == 0 )
str[i - pos + 1] = 1, pos = pi[pos], ++ret;
}
return ret;
}
int main()
{
int cnt = 0;
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
cin >> a+1 >> b+1;
prefix(a,pi);
cout << kmp(a,b,pi) << endl;
for ( int i = 1; b[i] && cnt < 1000; ++i )
if ( b[i] == 1 )
cout << i - 1 << " ", ++cnt;
return 0;
}