Cod sursa(job #1690148)

Utilizator preda.andreiPreda Andrei preda.andrei Data 14 aprilie 2016 20:20:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <cstdio>
#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()
{
    FILE *fin = fopen("strmatch.in", "r");
    FILE *fout = fopen("strmatch.out", "w");

    int len1, len2;

    len1 = citesteLinie(s1 + 1, fin);
    len2 = citesteLinie(s2 + 1, fin);

    kmp(len1, len2);

    fprintf(fout, "%d\n", npotriviri);
    for(int i = 1; i <= npotriviri; ++i)
        fprintf(fout, "%d ", 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;
    }

}

int citesteLinie(char s[], FILE *f){
    int len;

    fgets(s, 2000000, f);
    len = strlen(s);
    if(s[len - 1] == '\n'){
        s[len - 1] = '\0';
        --len;
    }
    return len;
}