Pagini recente » Cod sursa (job #1635622) | Cod sursa (job #345475) | Cod sursa (job #525292) | Cod sursa (job #2673422) | Cod sursa (job #930099)
Cod sursa(job #930099)
#include<cstdio>
#include<cassert>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int len1, len2;
char a[2000005], b[2000005];
void read(){
assert(freopen("strmatch.in", "r", stdin));
gets(a);
gets(b);
len1 = strlen(a);
len2 = strlen(b);
for(int i = len1; i > 0; --i)
a[i] = a[i - 1];
for(int i = len2; i > 0; --i)
b[i] = b[i - 1];
}
int t[2000005];
void prefix(){
t[1] = 0;
for(int i = 2; i <= len1; ++i){
int p = i - 1;
do{
p = t[p];
if(a[i] == a[p + 1]){
t[i] = p + 1;
break;
}
}while(p);
}
}
int matches, dp[2000005];
vector<int> ans;
void solve(){
prefix();
for(int i = 1; i <= len2; ++i){
int p = dp[i - 1];
if(a[p + 1] == b[i]){
dp[i] = p + 1;
continue;
}
do{
p = t[p];
if(b[i] == a[p + 1]){
dp[i] = p + 1;
break;
}
}while(p);
}
for(int i = 1; i <= len2; ++i)
if(dp[i] == len1){
++matches;
if(ans.size() < 1000)
ans.push_back(i - len1);
}
}
void write(){
assert(freopen("strmatch.out", "w", stdout));
printf("%d\n", matches);
for(int i = 0; i < ans.size(); ++i)
printf("%d ", ans[i]);
}
int main(){
read();
solve();
write();
return 0;
}