Cod sursa(job #2175044)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 16 martie 2018 14:54:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

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

char a[MAXN + 1], b[MAXN + 1];
int pi[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 k = 0;
    for(i = 2; i <= sza; i++) {
        while(k > 0 && a[k + 1] != a[i])
            k = pi[k];
        if(a[k + 1] == a[i])
            k++;
        pi[i] = k;
    }
    k = 0;
    int cnt = 0;
    for(i = 1; i <= szb; i++) {
        while(k > 0 && a[k + 1] != b[i])
            k = pi[k];
        if(a[k + 1] == b[i])
            k++;
        if(k == sza) {
            cnt++;
            if(cnt < 1000) {
                sol.push_back(i - sza);
            }
        }
    }
    fprintf(fout,"%d\n" ,cnt);
    for(auto it : sol) {
        fprintf(fout,"%d " ,it);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}