Cod sursa(job #3147245)

Utilizator nnmadalinNeauna Madalin nnmadalin Data 25 august 2023 00:13:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
//#define int long long 

const string FILE_NAME = "strmatch";
ifstream fin(FILE_NAME + ".in");
ofstream fout(FILE_NAME + ".out");

vector<int> lps(string s){
    vector<int> v_lps(s.size(), 0);

    int len = 0;
    for(int i = 1; i < s.size();){
        if(s[i] == s[len]){
            len++;
            v_lps[i] = len;
            i++;
        }
        else{
            if(len != 0){
                len = v_lps[len - 1];
            }
            else
                v_lps[i] = 0, i++;
        }
    }
    return v_lps;
}

signed main()
{
    string a,b;

    fin >> a >> b;

    int n = 0;
    vector <int> v_lps = lps(a);
    vector <int> answer;

    for(int i = 0, j = 0; i < b.size();){
        if(b[i] == a[j]){
            i++; j++;
            if(j == a.size()){
                n++;
                if(answer.size() < 1000)
                    answer.pb(i - j);
                j = v_lps[j - 1];
            }
        }
        else{
            if(j != 0){
                j = v_lps[j - 1];
            }
            else
                i++;
        }
    }

    fout << n << "\n";
    for(int i = 0; i < answer.size(); i++)
        fout << answer[i] << " ";

    return 0;
}