Pagini recente » Cod sursa (job #433442) | Cod sursa (job #1224111) | Cod sursa (job #446655) | Cod sursa (job #2081586) | Cod sursa (job #1246902)
#include <iostream>
#include <string.h>
#include <vector>
#define MAX 2000003
using namespace std;
int n, m;
char little[MAX], big[MAX];
vector<int> ans;
int dp[MAX];
void preprocess(){
dp[0] = 0;
dp[1] = 0;
int j;
for(int i = 2; i <= n; i++){
j = i-1;
while(j > 0 && little[i-1] != little[dp[j]]){
j = dp[j];
}
if(little[i-1] == little[dp[j]]){
dp[i] = dp[j] + 1;
}else{
dp[i] = (dp[j]);
}
}
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", little, big);
n = strlen(little);
m = strlen(big);
if(n > m){
printf("0\n");
return 0;
}
preprocess();
int j = dp[0], i = 0; // i - big string, j - little one
while(i < m){
if(little[j] == big[i]){
if(j == n-1){
j = dp[n];
ans.push_back(i - n + 1);
}else{
j++;
}
i++;
}else{
if(j > 0){
j = dp[j];
}else{
i++;
}
}
}
printf("%d\n", n = ans.size());
for(int i = 0; i < n; i++){
printf("%d ", ans[i]);
}
printf("\n");
return 0;
}