Pagini recente » Cod sursa (job #2574493) | Cod sursa (job #2196754) | Cod sursa (job #2797841) | Cod sursa (job #2536150) | Cod sursa (job #2081343)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
int sza, szb, aux[2000100], sol[1010], cnt;
void build(){
int i = 1, j = 2;
for(; j <= sza; j++){
while(a[j] != a[i] && i > 1)
i = aux[i - 1] + 1;
if(a[j] == a[i])
aux[j] = i++;
}
}
void solve(){
int i = 1, j = 1;
for(; j <= szb; j++){
while(b[j] != a[i] && i > 1)
i = aux[i - 1] + 1;
if(i == sza){
cnt++;
if(cnt <= 1000)
sol[cnt] = j - i;
}
if(b[j] == a[i])
i++;
}
out << cnt << '\n';
for(int i = 1; i <= min(1000, cnt); i++)
out << sol[i] << ' ';
}
int main(){
in >> a >> b;
sza = a.size();
szb = b.size();
a = '+' + a;
b = '+' + b;
build();
solve();
return 0;
}