Cod sursa(job #1968984)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 18 aprilie 2017 07:32:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 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;
 
int z[LGMAX];
 
vector<int> sol;
 
void calcul_z(){
    int left, right;
    left = right = 0;
    int n = k;
    for(int i = 1; i < n; i++){
        if(i > right){
            int  p = 0;
            while(s[p] == s[i + p] && p < n){
                p++;
            }
            if(!p){
                z[i] = 0;
                left = right = i;
            } else {
                --p;
                left = i;
                right = left + p;
                z[i] = right - left + 1;
            }
        } else {
            k = i - left;
            if(z[k] < right - i + 1)
                z[i] = z[k];
            else{
                left = i;
                int  p = right - i + 1;
                while(p < n && s[p] == s[right+1] && right < n -1)
                    ++right,  ++p;
                z[i] = right - left + 1;
            }
        }
    }
}
 
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];
    }
//    s[k++] = 0;
 
    calcul_z();
 
    for(int i = 0; i < m + n + 1; i++){
 
        if(z[i] == m)
            sol.push_back(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", sol.size());
    for(int x : sol)
        printf("%d ", x);
    return 0; 
}