Pagini recente » Cod sursa (job #1655518) | Cod sursa (job #2610468) | Cod sursa (job #1135409) | Cod sursa (job #2623680) | Cod sursa (job #1809197)
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <math.h>
#define N_MAX 2000002
using namespace std;
char a[N_MAX], b[N_MAX];
vector<int> sol;
int prim = 3, hash_a = 0, hash_b = 0;
bool flag = true;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
if (strlen(b) < strlen(a)) {
printf("0");
return 0;
}
fgets(a, N_MAX, stdin);
a[strlen(a) - 1] = '\0';
fgets(b, N_MAX, stdin);
int n1 = strlen(a), n2 = strlen(b);
for (int i = 0; i < n1; i ++) {
hash_a += pow(prim, i) * a[i];
hash_b += pow(prim, i) * b[i];
if (a[i] != b[i])
flag = false;
}
if (hash_a == hash_b && flag)
sol.push_back(0);
for (int i = n1; i < n2; i ++) {
hash_b -= b[i - n1];
hash_b /= prim;
hash_b += pow(prim, n1 - 1) * b[i];
if (hash_a == hash_b) {
flag = true;
for (int j = 0; j < n1; j ++)
if (a[j] != b[i - n1 + 1 + j])
flag = false;
if (flag)
sol.push_back(i - n1 + 1);
}
}
printf("%d\n", sol.size());
for (int i = 0; i < sol.size(); i ++)
printf("%d ", sol[i]);
printf("\n");
return 0;
}