Cod sursa(job #2833813)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 15 ianuarie 2022 19:00:36
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 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];

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

    for(int i=1; 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;
}