Pagini recente » Cod sursa (job #1266618) | Cod sursa (job #2282384) | Cod sursa (job #2049895) | Cod sursa (job #561079) | Cod sursa (job #1344253)
#include <fstream>
#include <cstring>
#define DIM 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[DIM], B[DIM];
int P[DIM], n, m, i, j, S[DIM], lenght, nr;
int main()
{
fin >> A + 1;
n = strlen(A + 1);
fin >> B + 1;
m = strlen(B + 1);
P[1] = 0;
lenght = 0;
for(i = 2; i <= n; i ++)
{
while(lenght && A[lenght + 1] != A[i])
lenght = P[lenght];
if(A[lenght + 1] == A[i])
lenght ++;
P[i] = lenght;
}
lenght = 0;
for(i = 1; i <= m; i ++)
{
while(lenght && A[lenght + 1] != B[i])
lenght = P[lenght];
if(A[lenght + 1] == B[i])
lenght ++;
if(lenght == n)
{
nr ++;
if(nr <= 1000)
S[nr] = i - lenght + 1;
lenght = P[lenght];
}
}
fout << nr << '\n';
if(nr > 1000)
nr = 1000;
for(i = 1; i <= nr; i ++)
fout << S[i] - 1 << " ";
return 0;
}