Pagini recente » Cod sursa (job #1466107) | Cod sursa (job #344506) | Cod sursa (job #1655527) | Cod sursa (job #113458) | Cod sursa (job #3144588)
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[NMAX], B[NMAX];
int d[NMAX], nA, nB, q;
int nr, p[NMAX];
void prefix()
{
d[1] = 0;
int q = 0;
for(int i = 2; i <= nA; i ++)
{
while(q && A[q + 1] != A[i])
q = d[q];
if(A[q + 1] == A[i])
q ++;
d[i] = q;
}
}
int main()
{
f.getline(A, NMAX);
f.getline(B, NMAX);
nA = strlen(A), nB = strlen(B);
for(int i = nA; i >= 1; i --)
A[i] = A[i - 1];
for(int i = nB; i >= 1; i --)
B[i] = B[i - 1];
prefix();
for(int i = 1; i <= nB; i ++)
{
if(q && A[q + 1] != B[i])
q = d[q];
if(A[q + 1] == B[i])
q ++;
if(q == nA)
{
nr ++;
q = d[nA];
p[i - nA] = 1;
}
}
g << nr << '\n';
int val = 0;
for(int i = 0; val != nr && val < 1000; i ++ )
if(p[i] == 1)
val ++, g << i << " ";
return 0;
}