Pagini recente » Cod sursa (job #775989) | Cod sursa (job #2622646) | Cod sursa (job #433103) | Cod sursa (job #1481860) | Cod sursa (job #790384)
Cod sursa(job #790384)
#include<cstdio>
#include<cassert>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
char text[1000005], pat[1000005], aux[1000005];
int l1, l2;
void read(){
assert(freopen("strmatch.in", "r", stdin));
gets(aux);
l2 = strlen(aux);
for(int i = 0; i < l2; ++i)
pat[i + 1] = aux[i];
gets(aux);
l1 = strlen(aux);
for(int i = 0; i < l1; ++i)
text[i + 1] = aux[i];
}
int pi[1000005];
void prefix(){
pi[1] = 0;
for(int i = 2; i <= l2; ++i){
int p = i - 1;
do{
p = pi[p];
if(pat[i] == pat[p + 1]){
pi[i] = p + 1;
break;
}
}while(p);
}
}
vector<int> ans;
int sol[1000005];
void solve(){
prefix();
for(int i = 1; i <= l1; ++i){
int p = sol[i - 1];
if (text[i] == pat[p + 1])
sol[i] = p + 1;
else
do{
p = pi[p];
if(text[i] == pat[p + 1]){
sol[i] = p + 1;
break;
}
}while(p);
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] - l2);
}
int main(){
read();
solve();
write();
return 0;
}