Pagini recente » Cod sursa (job #1906836) | Cod sursa (job #2983392) | Cod sursa (job #308791) | Cod sursa (job #424370) | Cod sursa (job #578505)
Cod sursa(job #578505)
#include<fstream>
using namespace std;
#define minim(a,b) ((a)<(b)?(a):(b))
const int MaxN = 2000005;
const int MaxX = 1000;
int N,M,nrsol,urm[MaxN],sol[MaxX+5];
char s[MaxN],p[MaxN];
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 && p[q+1] != s[i] )
q = urm[q];
if( p[q+1] == s[i] )
q++;
if( q == M )
{
nrsol++;
if( nrsol > MaxX )
continue;
sol[nrsol] = i-M;
}
}
}
int main()
{
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
f.getline(p+1,MaxN);
f.getline(s+1,MaxN);
f.close();
N = strlen(s+1);
M = strlen(p+1);
p[0] = s[0] = ' ';
kmp();
int m = minim(nrsol,MaxX);
g << nrsol << '\n';
for( int i = 1 ; i <= m ; i++ )
g << sol[i] << ' ';
g << '\n';
g.close();
return 0;
}