Pagini recente » Cod sursa (job #1889720) | Cod sursa (job #1174151) | Cod sursa (job #1550560) | Cod sursa (job #670868) | Cod sursa (job #1967501)
#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, ss;
int z[LGMAX];
int sol[LGMAX];
void calcul_z(){
int left, right;
left = right = 0;
for(int p = 1; p < k; p++){
if(k > right){
left = right = p;
while(right < k && s[right] == s[right - left])
right++;
z[p] = right - left;
right--;
} else {
int p1 = p - left;
if(z[p1] < right - p + 1)
z[p] = z[p1];
else {
left = p;
while(right < k && s[right] == s[right - left])
right++;
z[k] = right - left;
right--;
}
}
}
}
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];
}
calcul_z();
for(int i = 0; i < m + n + 1; i++){
if(z[i] == m)
sol[ss++]=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", ss);
for(int i = 0; i < ss && i < 1000; i++)
printf("%d ", sol[i]);
printf("\n");
return 0;
}