Pagini recente » Cod sursa (job #1152728) | Cod sursa (job #946672) | Cod sursa (job #1457880) | Cod sursa (job #1106689) | Cod sursa (job #1968984)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int LGMAX = 2000002;
char text[LGMAX], pattern[LGMAX], s[2 * LGMAX];
int n, m, k;
int z[LGMAX];
vector<int> sol;
void calcul_z(){
int left, right;
left = right = 0;
int n = k;
for(int i = 1; i < n; i++){
if(i > right){
int p = 0;
while(s[p] == s[i + p] && p < n){
p++;
}
if(!p){
z[i] = 0;
left = right = i;
} else {
--p;
left = i;
right = left + p;
z[i] = right - left + 1;
}
} else {
k = i - left;
if(z[k] < right - i + 1)
z[i] = z[k];
else{
left = i;
int p = right - i + 1;
while(p < n && s[p] == s[right+1] && right < n -1)
++right, ++p;
z[i] = right - left + 1;
}
}
}
}
void match(){
for(int i = 0; i < m; i++){
s[k++] = pattern[i];
}
s[k++]='$';
for(int i = 0; i < n; i++){
s[k++] = text[i];
}
// s[k++] = 0;
calcul_z();
for(int i = 0; i < m + n + 1; i++){
if(z[i] == m)
sol.push_back(i - m - 1);
}
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(pattern, LGMAX, stdin);
fgets(text, LGMAX, stdin);
n = strlen(text);
m = strlen(pattern);
if(text[n - 1] == '\n'){
text[n - 1] = 0;
--m;
}
if(pattern[m - 1] == '\n'){
pattern[m-1] = 0;
--m;
}
match();
printf("%d\n", sol.size());
for(int x : sol)
printf("%d ", x);
return 0;
}