Cod sursa(job #2175110)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 16 martie 2018 15:20:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = (int) 2e6 + 5;

char a[2 * MAXN + 1], b[MAXN + 1];
int z[2 * MAXN + 1];

vector <int> sol;

int main() {
    FILE *fi, *fout;
    int i;
    fi = fopen("strmatch.in" ,"r");
    fout = fopen("strmatch.out" ,"w");
    fgets(a + 1, MAXN, fi);
    fgets(b + 1, MAXN, fi);
    int sza = strlen(a + 1) - 1, szb = strlen(b + 1) - 1;
    int sz = sza + szb;
    for(i = 1; i <= szb; i++) {
        a[i + sza] = b[i];
    }
    int l = 0, r = 0;
    z[1] = sz;
    for(i = 2; i <= sz; i++) {
        if(r >= i) {
            z[i] = min(z[i - l + 1], r - i + 1);
        }
        while(i + z[i] <= sz && a[z[i] + 1] == a[i + z[i]])
            z[i]++;
        if(i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    int cnt = 0;
    for(i = sza + 1; i <= sz; i++) {
        if(z[i] >= sza) {
            cnt++;
            if(cnt <= 1000) {
                sol.push_back(i - sza - 1);
            }
        }
    }
    fprintf(fout,"%d\n" ,cnt);
    for(auto it : sol) {
        fprintf(fout,"%d " ,it);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}