Cod sursa(job #2910241)

Utilizator rares89_Dumitriu Rares rares89_ Data 18 iunie 2022 19:02:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[2000005], b[2000005];
int nr, p[2000005], ans[1005], l, n, m; // l = len

int main() {
    fin >> (a + 1);
    fin >> (b + 1);
    fin.close();
    p[1] = 0;
    n = strlen(a + 1), m = strlen(b + 1);
    for(int i = 2; i <= n; i++) {
        while(l != 0 && a[i] != a[l + 1]) {
            l = p[l];
        }
        if(a[i] == a[l + 1]) {
            l++;
        }
        p[i] = l;
    }
    l = 0;
    for(int i = 1; i <= m; i++) {
        while(l != 0 && b[i] != a[l + 1]) {
            l = p[l];
        }
        if(b[i] == a[l + 1]) {
            l++;
        }
        if(l == n) {
            nr++;
            if(nr <= 1000) {
                ans[nr] = i - n;
            }
            l = p[l];
        }
    }
    fout << nr << "\n";
    for(int i = 1; i <= min(nr, 1000); i++) {
        fout << ans[i] << " ";
    }
    return 0;
}