Pagini recente » Cod sursa (job #1180051) | Cod sursa (job #831671) | Cod sursa (job #2854092) | Cod sursa (job #2681826) | Cod sursa (job #997963)
Cod sursa(job #997963)
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int knmax = 2e6 + 6;
char a[knmax], b[knmax];
int l1, l2;
void read(){
gets(a);
gets(b);
l1 = strlen(a);
for(int i = l1; i > 0; --i)
a[i] = a[i - 1];
l2 = strlen(b);
for(int i = l2; i > 0; --i)
b[i] = b[i - 1];
a[0] = '*';
b[0] = '$';
}
int t[knmax];
void prefix(){
for(int i = 2; i <= l2; ++i){
int p = i - 1;
do{
p = t[p];
if(a[i] == a[p + 1]){
t[i] = p + 1;
break;
}
}while(p);
}
}
int nrsol, sol[knmax];
vector<int> ans;
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
read();
if(l1 > l2){
printf("0");
return 0;
}
prefix();
for(int i = 1; i <= l2; ++i){
int p = sol[i - 1];
if(b[i] == a[p + 1])
sol[i] = p + 1;
else
do{
p = t[p];
if(b[i] == a[p + 1]){
sol[i] = p + 1;
break;
}
}while(p);
if(sol[i] == l1){
++nrsol;
if(nrsol <= 1000)
ans.push_back(i - l1);
}
}
printf("%d\n", nrsol);
for(int i = 0; i < ans.size(); ++i)
printf("%d ", ans[i]);
return 0;
}