Pagini recente » Cod sursa (job #1246772) | Cod sursa (job #2837950) | Cod sursa (job #2854924) | Cod sursa (job #2964547) | Cod sursa (job #2277234)
#include <fstream>
#include <cstring>
#define NMAX 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i, j, pi[NMAX], lenA, lenB, q, poz[NMAX], nr;
char A[NMAX], B[NMAX];
void prefix() {
q = 0;
pi[1] = 0;
for (i = 2; i <= lenA; i++) {
while(q && A[i] != A[q + 1])
q = pi[q];
if(A[i] == A[q + 1])
q++;
pi[i] = q;
}
}
int main()
{
fin.getline(A, NMAX);
fin.getline(B, NMAX);
lenA = strlen(A);
lenB = strlen(B);
for (i = lenA; i >= 1; i--)
A[i] = A[i - 1];
A[0] = ' ';
for (i = lenB; i >= 1; i--)
B[i] = B[i - 1];
B[0] = ' ';
prefix();
q = 0;
for (i = 1; i <= lenB; i++) {
while(q && A[q + 1] != B[i])
q = pi[q];
if(A[q + 1] == B[i])
q++;
if(q == lenA) {
q = pi[lenA];
nr++;
if(nr <= 1000)
poz[nr] = i - lenA;
}
}
fout << nr << '\n';
for(i = 1; i <= nr && i <= 1000; i++)
fout << poz[i] << " ";
return 0;
}