Cod sursa(job #2763906)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 17 iulie 2021 18:45:30
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

vector<int> make_pattern(string s)
{
    vector<int>v (1,0);
    int i=0,j=1,match_size=0;
    while(j<s.size())
    {
        if(s[i]==s[j])
        {
            i++;
            j++;
            match_size++;
            v.push_back(match_size);
            continue;
        }
        else
        {
            i=v[i-1];
            j++;
            match_size=i;
            v.push_back(match_size);
            continue;
        }
    }

    return v;
}

void solve(string pattern, string text)
{
    vector<int> vp=make_pattern(pattern),ans{};
    int i_text=0,i_pattern=0,current_len=0;
    for(;i_text!=text.size();i_text++)
    {
        if(pattern[i_pattern]==text[i_text])
        {
            current_len++;
            i_pattern++;
        }
        else
        {
            if(i_pattern==0)
                i_pattern=vp[0];
            else
            i_pattern=vp[i_pattern-1];
            current_len=i_pattern;
        }

        if(i_pattern==pattern.size())
        {
            ans.push_back(i_text-pattern.size()+1);
            i_pattern=vp[i_pattern-1];
        }
    }

    fout<<ans.size()<<'\n';
    for(auto it:ans)
        fout<<it<<" ";
}

int main()
{
    vector<int>test=make_pattern("ABA");
    for(auto it:test)
        cout<<it<<" ";
    string a,b;
    fin>>a>>b;
    solve(a,b);
    return 0;
}