Cod sursa(job #3216828)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 19 martie 2024 23:05:41
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2000005;

char a[NMAX], b[NMAX];
int p[NMAX];
vector<int> rasp;

int main()
{
    fin >> (a+1);
    fin >> (b+1);

    int n = strlen(a+1);
    int m = strlen(b+1);

    p[1] = 0;

    for(int i=2;i<=n;i++){
        int curr_match = p[i - 1];
        while(a[i] != a[curr_match + 1] and curr_match != 0){
            curr_match = p[curr_match];
        }
        if(a[i] == a[curr_match + 1]) p[i] = curr_match + 1;
        else                          p[i] = 0;
    }

    int ind = 0;

    for(int i=1;i<=m;i++){

        while(b[i] != a[ind + 1] and ind != 0){
            ind = p[ind];
        }

        if(b[i] == a[ind+1]) ind++;
        if(ind == n){
            rasp.push_back(i-n);
            ind = p[ind];
        }

    }

    fout << rasp.size() << '\n';
    for(auto it: rasp){
        fout << it << ' ';
    }

    return 0;
}