Pagini recente » Cod sursa (job #1578592) | Cod sursa (job #250861) | Cod sursa (job #535859) | Cod sursa (job #2719799) | Cod sursa (job #1497793)
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAXN 4000500
#define MIN(a, b) (((a) < (b))?(a):(b))
using namespace std;
int na, n, z[MAXN], solcnt;
char s[MAXN];
vector<int> sol;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", s);
na = strlen(s);
s[na] = '$';
scanf("%s", s + na + 1);
n = strlen(s);
int l = 0, r = 0;
for(int i = 1; i < n; i++) {
if(r < i) {
int j, k;
for(j = i, k = 0; j < n && s[j] == s[k]; j++, k++);
z[i] = j - i;
if(i + z[i] - 1 > r) r = z[i], l = i;
}
else {
int x = i - l;
z[i] = MIN(z[x], r - i + 1);
int j, k;
for(j = i + z[i], k = z[i]; j < n && s[j] == s[k]; j++, k++);
z[i] = j - i;
if(i + z[i] - 1 > r) r = z[i], l = i;
}
if(i > na && z[i] == na) {
++solcnt;
if(sol.size() < 1000) sol.push_back(i - na - 1);
}
}
printf("%d\n", solcnt);
for(auto x: sol)
printf("%d ", x);
printf("\n");
return 0;
}