Pagini recente » Cod sursa (job #889925) | Cod sursa (job #2875649) | Cod sursa (job #161781) | Cod sursa (job #483007) | Cod sursa (job #2056625)
#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';
dim = min(dim, 1000);
for(int i = 1; i <= dim ; i++)
fout << rez[i] << ' ';
return 0;
}