Pagini recente » Istoria paginii runda/mexxx | Clasament 225200 | Clasament oji_2013_10 | Cod sursa (job #3001973) | Cod sursa (job #3001975)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> pos;
char a[2000005], b[2000005];
int n, m, pi[2000005];
void citire() {
fin>>(a+1)>>(b+1);
n=strlen(a+1);
m=strlen(b+1);
}
void prefix() {
int k=0;
for (int i=2; i<=n; i++) {
while (k && a[k+1]!=a[i])
k=pi[k];
if (a[k+1]==a[i])
k++;
pi[i]=k;
}
}
void kmp() {
int q=0;
for (int i=1; i<=m; i++) {
while (q && a[q+1]!=b[i])
q=pi[q];
if (a[q+1]==b[i])
q++;
if (q==n)
pos.push_back(i-n);
}
}
void afisare() {
fout<<pos.size()<<"\n";
int nr=0;
for (auto i: pos) {
nr++;
fout<<i<<" ";
if (nr>1000)
exit(0);
}
}
int main() {
citire();
prefix();
kmp();
afisare();
return 0;
}