Pagini recente » Cod sursa (job #861476) | Cod sursa (job #749300) | Cod sursa (job #40009) | Cod sursa (job #18271) | Cod sursa (job #871790)
Cod sursa(job #871790)
#include<cstdio>
#include<cassert>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
char a[2000005], b[2000005];
int l1, l2, p[2000005];
void read(){
assert(freopen("strmatch.in", "r", stdin));
gets(a);
gets(b);
l1 = strlen(a);
l2 = strlen(b);
for(int i = l1; i > 0; --i)
a[i] = a[i - 1];
for(int i = l2; i > 0; --i)
b[i] = b[i - 1];
}
void pref(){
p[1] = 0;
for(int i = 2; i <= l1; ++i){
int t = i - 1;
do{
t = p[t];
if(a[t + 1] == a[i]){
p[i] = t + 1;
break;
}
}while(t);
}
}
int ans, d[2000005];
vector<int> v;
void solve(){
pref();
for(int i = 1; i <= l2; ++i){
int t = d[i - 1];
if(a[t + 1] == b[i])
d[i] = t + 1;
else do{
t = p[t];
if(a[t + 1] == b[i]){
d[i] = t + 1;
break;
}
}while(t);
if(d[i] == l1){
++ans;
if(ans <= 1000)
v.push_back(i - l1);
}
}
}
void write(){
assert(freopen("strmatch.out" ,"w", stdout));
printf("%d\n", ans);
for(int i = 0; i < v.size(); ++i)
printf("%d ", v[i]);
}
int main(){
read();
solve();
write();
}