Pagini recente » Cod sursa (job #2391072) | Cod sursa (job #1869950) | Cod sursa (job #2301416) | Cod sursa (job #543972) | Cod sursa (job #2056601)
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#define DM 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[DM], k, n, m, dim, rez[DM];
char p[DM], t[DM];
int main()
{
fin >> p + 1 >> t + 1;
n = strlen(p + 1);
m = strlen(t + 1);
k = 0;
for(int i = 2; i <= n; i++){
while(k > 0 && p[k + 1] != p[i])
k = pi[k];
if(p[k + 1] == p[i])
++k;
pi[i] = k;
}
k = 0;
for(int i = 1; i <= m; i++){
while(k > 0 && p[k + 1] != t[i])
k = pi[k];
if(p[k + 1] == t[i])
++k;
if(k == n){
k = pi[k];
++dim;
if(dim < 1000)
rez[dim] = i - n;
}
}
fout << dim << '\n';
for(int i = 1; i <= dim; i++)
fout << rez[i] << ' ';
return 0;
}