Pagini recente » Cod sursa (job #584084) | Cod sursa (job #942189) | Cod sursa (job #2875688) | Cod sursa (job #2466130) | Cod sursa (job #1489518)
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX 2000010
#define MAX_PRINT 1000
int* pi;
int* pozitii;
int nr;
using namespace std;
void prefix(char* sir) {
int n = strlen(sir);
int k = -1;
pi[0] = -1;
for (int i = 1; i < n; i++) {
while (k > -1 && sir[k + 1] != sir[i]) {
k = pi[k];
}
if (sir[k + 1] == sir[i]) {
k++;
}
pi[i] = k;
}
}
void kmp(char* cautat, char* sir) {
int lungimeCautat = strlen(cautat);
int lungimeSir = strlen(sir);
int q = -1;
for (int i = 0; i < lungimeSir; i++) {
while (q > -1 && cautat[q + 1] != sir[i]) {
q = pi[q];
}
if (cautat[q + 1] == sir[i]) {
q++;
}
if (q + 1 == lungimeCautat) {
pozitii[nr] = i - lungimeCautat + 1;
nr++;
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
char* a = new char[MAX];
char* b = new char[MAX];
scanf("%s", a);
scanf("%s", b);
nr = 0;
pozitii = new int[MAX_PRINT];
pi = new int[MAX];
prefix(a);
kmp(a, b);
printf("%i\n", nr);
for (int i = 0; i < nr; i++) {
printf("%i ", pozitii[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}