Cod sursa(job #2977749)

Utilizator Andrei_Gagea08Andrei Gagea Andrei_Gagea08 Data 12 februarie 2023 13:16:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
/// strmatch de pe infoarena cu KMP

#include <fstream>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

char v[4000001];
int pi[2000001];

int main()
{
    int n=0,i,l,nrap=0;
    char ch;
    cin.get(ch);
    while(ch!='\n')
    {
        v[++n]=ch;
        cin.get(ch);
    }
    pi[1]=0;
    l=n;
    i=1;
    n++;
    v[n]='#';
    n++;
    cin.get(v[n+1]);
    n++;
    while(cin.get(v[n]))
    {
        i++;
        pi[i]=pi[i-1];
        while(pi[i]!=0 && v[pi[i]+1]!=v[n])
        {
            pi[i]=pi[pi[i]];
        }
        if(v[pi[i]+1]==v[n])
            pi[i]++;
        if(pi[i]==l)
            nrap++;
        n++;
    }
    n--;
    cout<<nrap;
    return 0;
}