Pagini recente » Cod sursa (job #1450330) | Cod sursa (job #645673) | Cod sursa (job #2118888) | Cod sursa (job #1261099) | Cod sursa (job #2281501)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
string a,b,s; int nr, alen, blen; int p[2000005]; int sol[2000005];
void prefix() {
int k, i;
k = 0;
p[1] = 0;
for(i = 2; i < alen; ++i) {
while((k > 0) && (a[i] != b[k+1])) {
k = p[k];
}
if(b[i] == a[k + 1]) {
++k;
}
p[i] = k;
}
}
int main() {
int i, q;
a += ' ';
b += ' ';
f>>s;
a += s;
f>>s;
b += s;
alen = a.length();
blen = b.length();
prefix();
q = 0; nr = 0; --alen;
for(i = 1; i < blen; ++i) {
while((q > 0) && (b[i] != a[q + 1])) {
q = p[q];
}
if(b[i] == a[q + 1]) {
++q;
}
if(q == alen) {
++nr;
sol[nr] = i - alen;
}
}
g<<nr<<'\n';
for(i = 1; i <= nr; ++i) {
g<<sol[i]<<' ';
}
return 0;
}