Cod sursa(job #1967501)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 16 aprilie 2017 18:55:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int LGMAX = 2000002;
char text[LGMAX],  pattern[LGMAX],  s[2 * LGMAX];
int n, m, k, ss;

int z[LGMAX];
int sol[LGMAX];

void calcul_z(){
    int left, right;
    left = right = 0;
    for(int p = 1; p < k; p++){
        if(k > right){
            left = right = p;
            while(right < k && s[right] == s[right - left])
                right++;
            z[p] = right - left;
            right--;
        } else {
            int p1 = p - left;
            if(z[p1] < right - p + 1)
                z[p] = z[p1];
            else {
                left = p;
                while(right < k && s[right] == s[right - left])
                    right++;
                z[k] = right - left;
                right--; 
            }
        }
    }
}

void match(){
    for(int i = 0; i < m; i++){
        s[k++] = pattern[i];
    }
    s[k++]='$';

    for(int i = 0; i < n; i++){
        s[k++] = text[i];
    }

    calcul_z();

    for(int i = 0; i < m + n + 1; i++){

        if(z[i] == m)
            sol[ss++]=i - m - 1;   
    } 
}

int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    fgets(pattern, LGMAX, stdin);
    fgets(text, LGMAX, stdin);

    n = strlen(text);
    m = strlen(pattern);

    if(text[n - 1] == '\n'){
        text[n - 1] = 0;
        --m;
    }

    if(pattern[m - 1] == '\n'){
        pattern[m-1] = 0;
        --m;
    }
    match();
    printf("%d\n", ss);
    for(int i = 0; i < ss && i < 1000; i++)
        printf("%d ", sol[i]);
    printf("\n");
    return 0;

}