Cod sursa(job #1131610)

Utilizator Theorytheo .c Theory Data 28 februarie 2014 22:06:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int NMAX = 2000009;

int N; int M; char A[NMAX]; char B[NMAX]; int pi[NMAX];

vector<int> Solution;

int main() {

    fin >> A + 1 >> B + 1;

    N = strlen(A + 1); M = strlen(B + 1);

    pi[1] = 0; int k = 0;

    for(int i = 2; i <= N; ++i) {
        while( k > 0 && A[k + 1] != A[i]) k = pi[k];

        if(A[k + 1] == A[i]) ++k;

        pi[i] = k;
    }

    k = 0; int count = 0;
    for(int i = 1; i <= M; ++i) {
        while(k > 0 && A[k + 1] != B[i]) k = pi[k];

        if(A[k + 1] == B[i]) ++k;

        if(k == N) {
            count++;
            if(count <= 1000)  Solution.push_back(i - N);

        }
    }

    fout << count << '\n';
    for(int i = 0; i < Solution.size(); ++i)
        fout << Solution[i] <<" ";

    return 0;
}