Cod sursa(job #1527745)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 18 noiembrie 2015 17:59:22
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
/**
    Given two strings made up of letters, find all the occurrences of string A in string B.
    1 <= length(A), length(B) <= 2,000,000
**/

#include <cstdio>
#include <cstring>
#include <algorithm>
 
#define NMAX 2000005
 
using namespace std;

int lengthA, lengthB; 
int parent[NMAX], occurrences, printString[NMAX];
char A[NMAX], B[NMAX];
 
void read() {
    A[0] = B[0] = '#';
    scanf("%s\n%s", A + 1);
    scanf("%s", B + 1);
    lengthA = strlen(A) - 1;
    lengthB = strlen(B) - 1;
}
 
void prefix() {
    int q = 0;
    for (int i = 2; i <= lengthA; ++i) {
        parent[i] = 0;
        while (q != 0 && A[i] != A[q + 1]) {
            q = parent[q];
        }
        if (A[i] == A[q + 1]) {
            q++;
        }
        parent[i] = q;
    }
}
 
void kmp() {
    int q = 0;
    for (int i = 1; i <= lengthB; ++i) {
        while (q != 0 && B[i] != A[q + 1]) {
            q = parent[q];
        }
        if (B[i] == A[q + 1]) {
            q++;
        }
        if (q == lengthA) {
            q = parent[q];
            occurrences++;
            if (occurrences <= 1000) {
                printString[occurrences] = i - lengthA;
            }
        }
    }
}
 
void print() {
    printf("%d\n", occurrences);
    for (int i = 1; i <= occurrences; ++i) {
        printf("%d ", printString[i]);
    }
}
 
int main() {
    read();
    prefix();
    kmp();
    print();
}