Cod sursa(job #2763917)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 17 iulie 2021 19:13:17
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 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();) {
        if (pattern[i_pattern] == text[i_text]) {
            current_len++;
            i_pattern++;
            i_text++;
        } else {
            if (i_pattern == 0)
                i_pattern = vp[0];
            else
                i_pattern = vp[i_pattern - 1];
            current_len = i_pattern;
            if (current_len != 0)
                i_text--;
            i_text++;
        }

        if (i_pattern == pattern.size()) {
            ans.push_back(i_text - pattern.size());
            i_pattern = vp[i_pattern - 1];
            current_len = i_pattern;
            if(ans.size()==1000)
                goto label;
        }
    }

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

int main() {

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