Pagini recente » Cod sursa (job #1125682) | Cod sursa (job #3175353) | Cod sursa (job #1372347) | Cod sursa (job #244720) | Cod sursa (job #1674760)
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int Max= 2000005;
char A[Max], B[Max];
int pref[Max];
int na,nb,num;
int rez[Max];
void calculprefixe()
{
int k=0,i;
for(i=2; i <= na; i++)
{
while(k>0 && A[k+1] != A[i])
k = pref[k];
if( A[k+1] == A[i] )
k++;
pref[i]=k;
}
}
void rezult()
{
int k=0;
for(int i=1; i <= nb; i++)
{
while(k>0 && A[k+1] != B[i])
k = pref[k];
if(A[k+1] == B[i])
k++;
if(k == na)
{
num++;
rez[num] = i - na + 1;
}
}
}
int main()
{
in >> (A + 1) >> (B + 1);
na = strlen( A+1 );
nb = strlen( B+1 );
if(na > nb)
{
out<<0;
return 0;
}
calculprefixe();
rezult();
out<< num << '\n';
for(int i=1; i<= min( num, 1000); i++)
out<< rez[i] - 1 << " ";
return 0;
}