Cod sursa(job #2857932)

Utilizator VladMxPMihaila Vlad VladMxP Data 26 februarie 2022 17:38:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#define PatternSizeMax 2000000

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s;
int nxt[PatternSizeMax],n;
int sol[PatternSizeMax],nrsol;

void prep_pattern(string s)
{
    nxt[0]=0;
    int j=0,i=1;
    while(i<n)
    {
        if(s[j]==s[i]) /// the characters are equal
        {
            nxt[i]=j+1;
            j++;
        }
        else /// we search for a previous equal character (or the character at index 0)
        {
            while(s[j]!=s[i] && j>0)
                j=nxt[j-1];
            if(s[j]==s[i])
                nxt[i]=j+1;
            else nxt[i]=j;
        }
        i++;
    }
}

void KMP()
{
    char c;
    int i=0,j=0;
    /// we read the text character by character
    while(fin>>c)
    {
        if(c==s[j]) /// we got pattern matched from 0 up to position j-1
            j++;
        else
        {
            while(c!=s[j] && j>0) /// we search for a previous character in pattern equal to c (or the character at index 0)
                j=nxt[j-1];
            if(c==s[j])
                j++;
        }
        if(j==n) /// we got a match
        {
            sol[++nrsol]=i-j+1;
        }
        i++;
    }
}

int main()
{
    fin>>s;
    n=s.length();
    prep_pattern(s);
    KMP();
    fout<<nrsol<<'\n';
    for(int i=1;i<=nrsol;i++)
        fout<<sol[i]<<" ";
}