Pagini recente » Cod sursa (job #385518) | Cod sursa (job #2380372) | Cod sursa (job #1728995) | Cod sursa (job #482821) | Cod sursa (job #1784214)
#include <fstream>
#include <string.h>
#define nMax 2000001
#define solMax 1001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lenA, lenB, nrSol;
int pi[nMax], Sol[solMax];
char A[nMax], B[nMax];
void make_prefix(char A[], int lenA)
{
int q=0;
for(int i=2; i<=lenA; i++)
{
while(q>0 && A[q+1]!=A[i])
q=pi[q];
if(A[q+1]==A[i])
q++;
pi[i]=q;
}
}
int str_match(char A[], int lenA, char B[], int lenB)
{
int q=0;
for(int i=1; i<=lenB; i++)
{
while(q>0 && A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i])
q++;
if(q==lenA)
{
nrSol++;
if(nrSol<solMax-1)
Sol[nrSol]=i-lenA;
q=pi[q];
}
}
}
void read()
{
fin>>(A+1), lenA=strlen(A+1);
fin>>(B+1), lenB=strlen(B+1);
}
void write()
{
fout<<nrSol<<'\n';
for(int i=1; i<=min(solMax, nrSol); i++)
fout<<Sol[i]<<" ";
}
void solve()
{
make_prefix(A, lenA);
str_match(A, lenA, B, lenB);
}
int main()
{
read();
solve();
write();
}