Cod sursa(job #1690156)

Utilizator preda.andreiPreda Andrei preda.andrei Data 14 aprilie 2016 20:25:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <cstring>

using namespace std;

char s1[2000005];
char s2[2000005];
int prefix[2000001];
int potriviri[1001];
int npotriviri;

int citesteLinie(char s[], FILE *f);
void kmp(int len1, int len2);
void formarePrefix(int len);

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

    int len1, len2;

    fin.getline(s1 + 1, 2000000);
    fin.getline(s2 + 1, 2000000);

    len1 = strlen(s1 + 1);
    len2 = strlen(s2 + 1);

    kmp(len1, len2);

    fout << npotriviri << "\n";
    for(int i = 1; i <= npotriviri; ++i)
        fout << potriviri[i] << " ";

    return 0;
}

void kmp(int len1, int len2){
    int k = 0;

    formarePrefix(len1);

    for(int i = 1; i <= len2; ++i){
        while(k > 0 && s2[i] != s1[k + 1])
            k = prefix[k];
        if(s2[i] == s1[k + 1])
            ++k;
        if(k == len1 && npotriviri < 1000){
            potriviri[++npotriviri] = i - len1;
        }
    }
}

void formarePrefix(int len){
    int k = 0;

    prefix[1] = 0;
    for(int i = 2; i <= len; ++i){
        while(k > 0 && s1[i] != s1[k + 1])
            k = prefix[k];
        if(s1[i] == s1[k + 1])
            ++k;
        prefix[i] = k;
    }

}