Pagini recente » Cod sursa (job #2685692) | Cod sursa (job #821812) | Cod sursa (job #2920333) | Cod sursa (job #1726919) | Cod sursa (job #1674745)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int dmax = 2000001;
char A[1 + dmax], B[1 + dmax];
int pref[dmax];
int r[dmax];
int nr;
int N, M;
void prefix()
{
int k = 0, i;
for(i = 2; i <= M; i++)
{
while(k != 0 && A[1 + k] != A[i]) k = pref[k];
if(A[i] == A[1 + k]) k++;
pref[i] = k;
}
}
void solve()
{
int k = 0, i;
for(i = 1; i <= N; i++)
{
while(k !=0 && A[k + 1] != B[i]) k = pref[k];
if(B[i] == A[1 + k]) k++;
if(k == M) r[++nr] = i - M;
}
}
void write()
{
int i;
out << nr << '\n';
if(nr > 1000) nr = 1000;
for(i = 1; i <= nr; i++) out << r[i] << " ";
}
int main()
{
in.getline(1 + A, dmax);
in.getline(1 + B, dmax);
M = strlen(1 + A);
N = strlen(1 + B);
prefix();
solve();
write();
return 0;
}