Cod sursa(job #2879576)

Utilizator CozminelDanielLupu Cosmin-Daniel CozminelDaniel Data 28 martie 2022 19:12:22
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <iostream>
#include <cstring>
#define N 2000005

using namespace std;

char pattern[N], str[N];
int pi[N];

void read() {
    ifstream f("strmatch.in");
    f >> pattern;
    f >> str;
    f.close();
}

void buildPi(char s[]) {
    int len = 0;
    pi[0] = 0;
    int i = 1;
    int patSize = strlen(s);
    while (i < patSize) {
        if (s[i] == s[len]) {
            len++;
            pi[i] = len;
            i++;
        }
        else {
            if (len != 0)
                len = pi[len - 1];
            else {
                pi[i] = 0;
                i++;
            }
        }
    }
}

void solve() {
    ofstream g("strmatch.out");
    read();
    int sol[N], k;
    k = 0;
    buildPi(pattern);
    int patSize = strlen(pattern) + 1;
    pattern[patSize] = NULL;
    for(int i = patSize - 1; i > 0; --i) {
        pattern[i] = pattern[i - 1];
        pi[i] = pi[i - 1];
    }
    pattern[0] = '0';
    int i = 0, j = 0;
    while(i < strlen(str)) {
        if(pattern[j + 1] == NULL) {
            sol[k++] = i - j;
            j = pi[j];
        }
        if(str[i] != pattern[j + 1]) {
            i++;
            j = pi[j];
        }
        else {
            i++;
            j++;
        }
    }
    g << k << "\n";
    for(int i = 0; i < k; ++i)
        g << sol[i] << " ";
    g.close();
}

int main() {
    solve();
    return 0;
}