Pagini recente » Cod sursa (job #1182486) | Cod sursa (job #1553610) | Cod sursa (job #2836199) | Cod sursa (job #2647724) | Cod sursa (job #1263367)
#include <iostream>
#include <string.h>
#include <fstream>
#define maxLength 2000010
using namespace std;
ifstream ji("strmatch.in");
ofstream jo("strmatch.out");
char A[maxLength], B[maxLength];
int sol[1005], pi[maxLength], m, n, total;
void buildPrefix()
{
int i, q=0;
for (i=2, pi[1]=0; i<=m; i++)
{
while (q && A[q+1]!=A[i])
q = pi[q];
if (A[q+1]==A[i])
q++;
pi[i]=q;
}
}
void solve()
{
int q=0;
for (int i=1; i<=n; i++)
{
while (q && A[q+1]!=B[i])
q = pi[q];
if (A[q+1]==B[i])
q++;
if (q==m)
{
q=pi[m];
if (total<1000)
sol[total]=i-m;
total++;
}
}
}
void show()
{
jo << total << "\n";
for (int i=0; i< (total<1000 ? total:1000); i++)
jo << sol[i] << " ";
}
int main()
{
ji >> (A+1) >> (B+1);
m=strlen(A+1);
n=strlen(B+1);
buildPrefix();
solve();
show();
return 0;
}
/*
* 6
* 7 9 11 13 15 31
*/