Pagini recente » Cod sursa (job #2901588) | Cod sursa (job #1004529) | Cod sursa (job #2830806) | Cod sursa (job #990082) | Cod sursa (job #2081337)
#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)
sol[++cnt] = j - i;
if(b[j] == a[i])
i++;
if(cnt > 1000)
break;
}
out << cnt << '\n';
for(int i = 1; i <= cnt; i++)
out << sol[i] << ' ';
}
int main(){
in >> a >> b;
sza = a.size();
szb = b.size();
a = '+' + a;
b = '+' + b;
build();
solve();
return 0;
}