Pagini recente » Cod sursa (job #366834) | Cod sursa (job #267439) | Cod sursa (job #703798) | Cod sursa (job #3129767) | Cod sursa (job #1428189)
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAXS 4000005
#define MIN(a, b) (((a) < (b))?(a):(b))
using namespace std;
int n, z[MAXS], l, r;
char s[MAXS];
vector<int> sol;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i;
scanf("%s\n", s + 1);
n = strlen(s + 1);
scanf("%s", s + n + 1);
l = 1; r = 0;
for(i = 2; s[i] != '\0'; i++) {
if(i > r) {
l = i; r = i - 1;
while(s[r + 1] == s[r - l + 2]) ++r;
z[i] = r - l + 1;
}
else {
int x = i - l + 1;
if(z[x] < r - i + 1)
z[i] = z[x];
else {
l = i;
while(s[r + 1] == s[r - l + 2]) r++;
z[i] = r - l + 1;
}
}
if(z[i] >= n)
sol.push_back(i - n - 1);
}
printf("%d\n", sol.size());
for(i = 0; i < sol.size() && i < 1000; i++)
printf("%d ", sol[i]);
printf("\n");
return 0;
}