Pagini recente » Cod sursa (job #1290742) | Cod sursa (job #738842) | Cod sursa (job #3211189) | Cod sursa (job #2964377) | Cod sursa (job #1245670)
#include <iostream>
#include <string.h>
#include <vector>
#define MAX 2000003
using namespace std;
int n, m;
char little[MAX], big[MAX];
vector<int> dp(MAX), ans;
void preprocess(){
dp[0] = 0;
for(int i = 1; i <= n; i++){
if(dp[i-1] != i-1 && little[dp[i-1]] == little[i-1]){
dp[i] = dp[i-1] + 1;
}else{
dp[i] = dp[i-1];
}
}
}
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;
}