Cod sursa(job #2833818)

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

using namespace std;

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

const int DIM = 2e6 + 50;

int sol, st, dr;
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;
    }

    for(int i=b.size()+2; i < (int)a.size(); i++)
        if(kmp[i] == (int)b.size()){
            sol++;
            if(sol == 1){
                st = i - (int)b.size() - 2 - (int)b.size() + 1;
                dr = i - (int)b.size() - 2;
            }
        }

    fout<<sol<<"\n"<<st<<" "<<dr;
    return 0;
}