Cod sursa(job #1429675)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 6 mai 2015 22:14:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#define DIM 2097152
using namespace std;

ifstream fin ("strmatch.in" );
ofstream fout("strmatch.out");

int N, M, C[DIM], P[DIM], i; char A[DIM], B[DIM];

inline void KMP(char A[], char B[], int C[], int P[], int N, int M){
    int L = 0, i;
    for(i = 2; i <= N; i ++){
        while(L != 0 && A[i] != A[L+1])
            L = P[L];
        if(A[i] == A[L+1])
            L ++;
        P[i] = L;
    }
    L = 0;
    for(i = 1; i <= M; i ++){
        while(L != 0 && B[i] != A[L+1])
            L = P[L];
        if(B[i] == A[L+1])
            L ++;
        if(L == N){
            C[++C[0]] = i - N;
            L = P[L];
        }
    }
    return;
}

int main(){
    fin >> A + 1;
    N = strlen(A + 1);
    fin >> B + 1;
    M = strlen(B + 1);
    KMP(A, B, C, P, N, M);
    fout << C[0] << "\n";
    for(i = 1; i <= min(C[0], 1000); i ++)
        fout << C[i] << " ";
    return 0;
}