Pagini recente » Cod sursa (job #461891) | Cod sursa (job #499788) | Cod sursa (job #2522085) | Cod sursa (job #1580188) | Cod sursa (job #790066)
Cod sursa(job #790066)
#include<cstdio>
#include<cassert>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int l1, l2;
char text[1000005], pat[10000005], aux[1000005];
void read(){
assert(freopen("strmatch.in", "r", stdin));
gets(aux);
l1 = strlen(aux);
for(int i = 0; i < l1; ++i)
pat[i + 1] = aux[i];
gets(aux);
l2 = strlen(aux);
for(int i = 0; i < l2; ++i)
text[i + 1] = aux[i];
}
int z[1000005];
void pre(){
int best = 0;
for(int i = 1; i <= l2; ++i){
if(best + z[best] >= i)
z[i]= min(z[i - best + 1], best + z[best] -i);
while(i + z[i] <= l2 && pat[i + z[i]] == pat[z[i] + 1])
++z[i];
if(i + z[i] >= best + z[best])
best = i;
}
}
vector<int> ans;
int sol[1000005];
void solve(){
pre();
int best = 0;
for(int i = 0; i <= l1; ++i){
if(best + sol[best] >= i)
sol[i] = min(z[i - best + 1], best + sol[best] - i);
while(i + sol[i] <= l2 && sol[i] + 1 <= l1 && text[i + sol[i]] == pat[sol[i] + 1])
++sol[i];
if(i + sol[i] >= best + sol[best])
best = i;
if(sol[i] == l2)
ans.push_back(i);
}
}
void write(){
assert(freopen("strmatch.out", "w", stdout));
printf("%d\n", ans.size());
int lim = ans.size();
lim = min(lim, 999);
for(int i = 0; i <= lim; ++i)
printf("%d ",ans[i]);
}
int main(){
read();
solve();
write();
return 0;
}