Cod sursa(job #1964617)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 13 aprilie 2017 16:07:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<fstream>
#include<cstring>
#define DIM 2000005
using namespace std;
int n, m, st, dr, poz, i, j, nr;
char s[2 * DIM], a[DIM];
int p[2 * DIM], sol[1005];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main(){
    fin>> s + 1;
    m = strlen(s + 1);
    fin>> a + 1;
    n = strlen(a + 1);
    for(i = m + 1; i <= n + m; i++){
        s[i] = a[i - m];
    }
    n += m;
    for(i = 2; i <= n; i++){
        if(dr < i){
            j = 1;
            while(j <= n && s[j] == s[i + j - 1]){
                j++;
            }
            j--;
            p[i] = j;
            dr = i + j - 1;
            st = i;
            if(p[i] >= m && i > m){
                nr++;
                if(nr <= 1000){
                    sol[nr] = i;
                }
            }
            continue;
        }
        poz = i - st + 1;
        if(poz + p[poz] - 1 < dr - st + 1){
            p[i] = p[poz];
        }
        else{
            j = dr - st + 1;
            while(j <= n && s[j] == s[i + j - 1]){
                j++;
            }
            j--;
            p[i] = j;
        }
        if(i + p[i] - 1 > dr){
            st = i;
            dr = i + p[i] - 1;
        }
        if(p[i] >= m && i > m){
            nr++;
            if(nr <= 1000){
                sol[nr] = i;
            }
        }
    }
    fout<< nr <<"\n";
    for(i = 1; i <= min(1000, nr); i++){
        fout<< sol[i] - m - 1 <<" ";
    }
    return 0;
}