Pagini recente » Cod sursa (job #1267226) | Cod sursa (job #1143758) | Cod sursa (job #1578476) | Cod sursa (job #1066426) | Cod sursa (job #1759152)
#include <fstream>
#include <string.h>
#include <vector>
#define nMax 2000001
#define solMax 1001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, Sol;
int vect[solMax], pref[nMax];
char A[nMax], B[nMax];
void make_prefix(char A[], int len)
{
int q=0;
pref[1]=0;
for(int i=2; i<=len; i++)
{
while(q!=0 && A[q+1]!=A[i])
q=pref[q];
if(A[q+1]==A[i])
q++;
pref[i]=q;
}
}
void match(char A[], char B[], int lenF, int lenS)
{
int q=0;
for(int i=1; i<=lenS; i++)
{
while(q!=0 && A[q+1]!=B[i])
q=pref[q];
if(A[q+1]==B[i])
q++;
if(q==lenF)
{
q=pref[q];
Sol++;
if(Sol<solMax)
vect[Sol]=i-lenF;
}
}
}
void write()
{
fout<<Sol<<'\n';
for(int i=1; i<=min(Sol, 1000); i++)
fout<<vect[i]<<" ";
}
int main()
{
fin>>A+1>>B+1;
n=strlen(A+1);
m=strlen(B+1);
make_prefix(A, n);
match(A, B, n, m);
write();
}