Pagini recente » Cod sursa (job #3241448) | Cod sursa (job #867314) | Cod sursa (job #2779168) | Cod sursa (job #1644184) | Cod sursa (job #662421)
Cod sursa(job #662421)
#include<fstream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MaxN = 2000001;
const int MaxM = 1001;
const char InFile[] = "strmatch.in";
const char OutFile[] = "strmatch.out";
int n,m,nrsol,urm[MaxN],sol[MaxM];
char S[MaxN],P[MaxN];
ifstream fin(InFile);
ofstream fout(OutFile);
void kmp()
{
int i,k,q;
urm[1] = 0;
k = 0;
for( q = 2; q <= m ; q++ )
{
while( k != 0 && P[q] != P[k+1] )
k = urm[k];
if( P[q] == P[k+1] )
++k;
urm[q] = k;
}
q = m+1;
for( i = 1 ; i <= n ; i++ )
{
while( q != 0 && S[i] != P[q+1] )
q = urm[q];
if( S[i] == P[q+1] )
++q;
if( q == m )
{
++nrsol;
if( nrsol > MaxM-1 )
continue;
sol[nrsol] = i - m;
}
}
}
int main()
{
fin.getline( P+1 , MaxN );
fin.getline( S+1 , MaxN );
fin.close();
n = strlen(S+1);
m = strlen(P+1);
kmp();
fout << nrsol << '\n';
for( int i = 1 ; i <= nrsol && i < MaxM ; i++ )
fout << sol[i] << ' ';
fout << '\n';
fout.close();
return 0;
}