Cod sursa(job #2764073)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 19 iulie 2021 11:39:55
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

vector<int> make_pattern(string a) {
    vector<int> pattern(1, 0);
    int i = 1, j = 0;
    while (i != a.size()) {
        if (a[i] == a[j]) {
            i++;
            j++;
            pattern.push_back(j);
            continue;
        } else {
            for (j = pattern[j - 1]; j != 0; j = pattern[j - 1]) {
                if (a[j] == a[i]) {
                    i++;
                    j++;
                    pattern.push_back(j);
                    break;
                }

            }
            if (j == 0) {
                pattern.push_back(0);
                i++;
            }
        }
    }

    return pattern;
}

void solve(string pattern, string text)
{
    vector<int> vp=make_pattern(pattern),ans={};
    int i_text=0,i_pattern=0;
    for(;i_text!=text.size();i_text++)
    {
        if(pattern[i_pattern]==text[i_text])
            i_pattern++;
        else
            i_pattern=vp[i_pattern-1];
        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() {
    string a,b;
    fin>>a>>b;
    solve(a,b);
    return 0;
}