Cod sursa(job #2833833)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 15 ianuarie 2022 19:18:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 2e6 + 50;

int len, kmp[ 2 * DIM];
string a, b;

int main (){
    fin>>b>>a;
    a = " " + b + "$" + a;

    kmp[1] = 0;
    for(int i=2; i < (int)a.size(); i++){
        len = kmp[i-1];

        while(a[len+1] != a[i] && len > 0)
            len = kmp[len];

        if(a[len+1] == a[i])
            kmp[i] = len + 1;
        else
            kmp[i] = 0;
    }

    int sol = 0;
    queue<int> start;

    for(int i=(int)b.size()+2; i < (int)a.size(); i++)
        if(kmp[i] == (int)b.size()){
            sol++;
            if(sol <= 1000)
                start.push(i - 1 - 2*(int)b.size());
        }

    fout<<sol<<"\n";
    while(!start.empty()){
        fout<<start.front()<<" ";
        start.pop();
    }
    return 0;
}