Cod sursa(job #1968983)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 18 aprilie 2017 07:27:51
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;
 
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){
            left = right = i;
            while(right < n && s[right-left] == s[right])
                ++right;
            z[i] = right-left;
            right--;
        } else {
            k = i - left;
            if(z[k] < right - i + 1)
                z[i] = z[k];
            else{
                left = i;
                while(right < n && s[right-left] == s[right])
                    ++right;
                z[i] = 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];
    }
//    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; 
}