Pagini recente » Cod sursa (job #724035) | Cod sursa (job #1906368) | Cod sursa (job #1663393) | Cod sursa (job #2796939) | Cod sursa (job #1089647)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;
const int knmax = 2e6 + 5;
char a[knmax], b[knmax];
int sza, szb, t[knmax];
void get_pref(char *v){
memset(t, 0, sizeof(t));
t[0] = t[1] = 0;
szb = strlen(v + 1);
for(int i = 2; i <= szb; ++i){
int p = i - 1;
do{
p = t[p];
if(v[p + 1] == v[i]){
t[i] = p + 1;
break;
}
}while(p);
}
}
int dp[knmax];
pair<int, vector<int> > first_1k_or_less(char *v, char *u){
memset(dp, 0, sizeof(dp));
sza = strlen(v + 1);
get_pref(u);
vector<int> ans;
int many = 0;
dp[0] = 0;
for(int i = 1; i <= sza; ++i){
int p = dp[i - 1];
do{
p = t[p];
if(u[p + 1] == v[i]){
dp[i] = p + 1;
break;
}
}while(p);
if(u[dp[i - 1] + 1] == v[i])
dp[i] = dp[i - 1] + 1;
if(dp[i] == szb){
++many;
if(many <= 1000)
ans.push_back(i - szb);
}
}
return mp(many, ans);
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(b + 1);
gets(a + 1);
pair<int, vector<int> > ans = first_1k_or_less(a, b);
printf("%d\n", ans.f);
for(int i = 0; i < ans.s.size(); ++i)
printf("%d ", ans.s[i]);
return 0;
}