Cod sursa(job #2040937)

Utilizator Mihai99Berechet Mihai Mihai99 Data 16 octombrie 2017 18:25:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

char P[2000005], T[2000005];

int main() {

    fin.getline(P, 2000005);
    fin.getline(T, 2000005);

    int lprefix[strlen(P)],
        k = 0;
    lprefix[0] = 0;

    for(int i = 1; i < strlen(P); ++i) {
        while(k > 0 && P[i] != P[k])
            k = lprefix[k-1];

        if(P[i] == P[k]) k += 1;
        lprefix[i] = k;
    }

//    for(int i = 0; i < strlen(P); ++i) {
//        cout<<lprefix[i]<<' ';
//    }

    vector<int> aparitii;

    k = 0;
    for(int i = 0; i < strlen(T); ++i) {
        while(k > 0 && T[i] != P[k]) {
            k = lprefix[k-1];
        }
        if(T[i] == P[k]) ++k;

        if(k == strlen(P)) {
            aparitii.push_back(i - k + 1);
            k = lprefix[k-1];
        }
    }

    fout<<aparitii.size()<<'\n';
    for(vector<int> :: iterator it = aparitii.begin(); it != aparitii.end(); ++it) {
        fout<<*it<<' ';
        if(it - aparitii.begin() == 999)
            break;
    }

    fin.close();
    fout.close();
    return 0;
}