Cod sursa(job #2764099)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 19 iulie 2021 14:35:08
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 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 mask, string text) {
    vector<int> pat = make_pattern(mask), ans{};
    int ip = 0, it = 0;

    for(;it!=text.size();it++)
    {
        if(ip==mask.size())
        {
            ans.push_back(it-mask.size());
            ip=pat[ip-1];
        }

        if(mask[ip]==text[it])
        {
            ip++;
            continue;
        }
        else
        {
            while(mask[ip]!=text[it] && ip!=0)
            {
                ip=pat[ip-1];
                if(mask[ip+1]==text[it])
                {
                    ip++;
                    break;
                }
            }
        }
    }
    fout<<ans.size()<<'\n';
    for(auto it:ans)
        fout<<it<<" ";

}

int main() {
    string a, b;
    fin>>a>>b;
    solve(a,b);
    return 0;
}