Pagini recente » Cod sursa (job #3128139) | Cod sursa (job #1094118) | Cod sursa (job #2448551) | Cod sursa (job #371280) | Cod sursa (job #1784237)
#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;
}
}
void 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)
Sol[nrSol]=i-lenA;
q=pi[q];
}
}
}
void read()
{
fin>>(A+1);
fin>>(B+1);
lenA=strlen(A+1);
lenB=strlen(B+1);
}
void write()
{
fout<<nrSol<<'\n';
for(int i=1; i<=min(1000, nrSol); i++)
fout<<Sol[i]<<" ";
}
void solve()
{
make_prefix(A, lenA);
str_match(A, lenA, B, lenB);
}
int main()
{
read();
solve();
write();
}