Pagini recente » Cod sursa (job #2772890) | Cod sursa (job #2861995) | Cod sursa (job #103827) | Cod sursa (job #1216191) | Cod sursa (job #2195712)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int sza, szb, rs, aux[2000100];
string a, b;
vector <int> sol;
void build(){
int i = 1, j = 2;
while(j <= sza){
while(i > 1 && a[j] != a[i])
i = aux[i - 1] + 1;
if(a[j] == a[i])
aux[j] = i++;
j++;
}
}
void kmp(){
int i = 1, j = 1;
while(j <= szb){
while(i > 1 && b[j] != a[i])
i = aux[i - 1] + 1;
if(i == sza){
rs++;
if(rs <= 1000)
sol.push_back(j - i);
}
if(b[j] == a[i])
i++;
j++;
}
}
int main(){
in >> a >> b;
sza = a.size();
szb = b.size();
a = '+' + a;
b = '+' + b;
build();
kmp();
out << rs << '\n';
for(auto i : sol)
out << i << ' ';
return 0;
}