Cod sursa(job #3238979)

Utilizator Allie28Radu Alesia Allie28 Data 1 august 2024 02:37:36
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <climits>

using namespace std;

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

const int LMAX = 2000005;

char a[LMAX], b[LMAX];
int pi[LMAX], sol[1005];
int n, m;

//pi[i] --> lungimea celui mai lung prefix sufix

void Pi(){
    int i, k;
    k = 0;
    for (i = 2; i <= n; i++) {
        while (k && a[k + 1] != a[i]) {
            k = pi[k];
        }
        if (a[k + 1] == a[i]) {
            k++;
        }
        pi[i] = k;
    }
}

int main() {
    fin.get(a + 1, LMAX);
    fin.get();
    fin.get(b + 1, LMAX);
    n = strlen(a + 1);
    m = strlen(b + 1);
    Pi();
    int k = 0, i;
    sol[0] = 0;
    for (i = 2; i <= m; i++) {
        while (k && a[k + 1] != b[i]) {
            k = pi[k];
        }
        if (a[k + 1] == b[i]) k++;
        if (k == n) {
            sol[0]++;
            if (sol[0] <= 1000) sol[sol[0]] = i;
        }
    }
    int ap = sol[0];
    fout<<ap<<"\n";
    for (i = 1; i <= ap && i <= 1000; i++) {
        fout<<sol[i] - n<<" ";
    }


    fin.close();
    fout.close();
    return 0;
}