Cod sursa(job #1148232)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 20 martie 2014 16:52:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>

#include <cstring>
using namespace std;

const int MAX_LEN = 2000002;

int N, M, ans = 0;
int Pi[MAX_LEN];
vector < int > sol;
char A[MAX_LEN], B[MAX_LEN];

void prefix() {
    for(int i = 2, p = 0; i <= N; ++i) {
        while(p > 0 && A[p + 1] != A[i])
            p = Pi[p];
        if(A[p + 1] == A[i])
            ++p;
        Pi[i] = p;
    }
}

void KMP() {
    for(int i = 1, p = 0; i <= M; ++i) {
        while(p > 0 && A[p + 1] != B[i])
            p = Pi[p];
        
        if(A[p + 1] == B[i])
            ++p;

        if(p == N) {
            if(ans < 1000)
                sol.push_back(i - N);
            ++ans;
        }
    }
}

int main() {
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    
    A[0] = B[0] = ' ';
    f >> (A + 1);
    f >> (B + 1);
    
    N = strlen(A) - 1, M = strlen(B) - 1;
    
    prefix();
    KMP();
    
    g << ans << "\n";
    for(size_t i = 0; i < sol.size(); ++i)
        g << sol[i] << " ";
    g << "\n";

    f.close();
    g.close();

    return 0;
}