Pagini recente » Cod sursa (job #1677695) | Cod sursa (job #511302) | Cod sursa (job #3222923) | Cod sursa (job #1985304) | Cod sursa (job #754422)
Cod sursa(job #754422)
#include<cstdio>
#include<string>
#include<vector>
#include<fstream>
#include<algorithm>
using namespace std;
#define NMAX 20000200
int sz = 0, p_sz = 0;
char P[NMAX],S[NMAX];
int *PI;
void compute_pie()
{
PI = (int*) calloc ( p_sz , sizeof(int) );
PI[0] = 0;
int i , k = 0;
for( i = 1; i < p_sz; ++i )
{
while( k > 0 && P[k] != P[i] )
k = PI[k];
if( P[k] == P[i] )
++k;
PI[i] = k;
}
}
int main()
{
fstream f ("strmatch.in", fstream::in );
//fstream g ("strmatch.out", fstream::out );
//freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
f.getline(P,NMAX);
f.getline(S,NMAX);
//fgets(P,NMAX,stdin);
//fgets(S,NMAX,stdin);
while( P[p_sz] ) ++p_sz;
while( S[sz] ) ++sz;
compute_pie();
int ans[1024], ans_count = 0;
int i, matched = 0;
for( i = 0; i < sz; ++i )
{
while( matched > 0 && P[ matched ] != S[i] )
matched = PI[ matched -1 ];
if( P[ matched ] == S[i] )
++matched;
if( matched == p_sz )
{
if( ans_count < 1001 )
ans[ ans_count ] = i - p_sz + 1;
++ans_count;
}
}
printf("%d\n",ans_count);// << "\n";
sz = min( ans_count, 1000 );
for( i = 0; i < sz; ++i )
printf("%d ", ans[ i ] );// << " ";
printf("\n");
//g << "\n";
return 0;
}