Pagini recente » Cod sursa (job #1418404) | Cod sursa (job #1313397) | Cod sursa (job #445516) | Cod sursa (job #2062207) | Cod sursa (job #348483)
Cod sursa(job #348483)
#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;
ifstream f1(fin);
ofstream f2(fout);
f1 >> a+1 >> b+1;
prefix(a,pi);
f2 << kmp(a,b,pi) << endl;
for ( int i = 1; b[i] && cnt < 1000; ++i )
if ( b[i] == 1 )
f2 << i - 1 << " ", ++cnt;
return 0;
}