Cod sursa(job #3257709)

Utilizator Stefan_NicaStefan Nica Stefan_Nica Data 18 noiembrie 2024 22:57:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
#define ull unsigned long long 
#define ll long long

std::ifstream f("strmatch.in");
std::ofstream g("strmatch.out");

void solve(); 
int main(){
    std::cin.tie(NULL);
    std::ios_base::sync_with_stdio(false);
    
    std::string s, pat;
    f>>pat>>s;
    std::vector<int> lps(pat.size() + 1), res;
    int i = 1, len = 0; lps[0] = 0;
    while(i < pat.length())
        if(pat[i] == pat[len])
            lps[i ++] = ++ len;
        else 
            if(len == 0)
                lps[i ++] = 0;
            else 
                len = lps[len - 1];
    int j = 0, ans = 0;
    for(i = 0; i < s.size(); ++i)
        if(s[i] == pat[j]){
            ++j; 
            if(j == pat.size()){
                res.push_back(i - j), j = lps[j - 1];
            }
        
        }
        else
            if(j)
                j = lps[j - 1], -- i;
    g<<res.size()<<'\n';
    for(auto i : res)
        g<<i + 1<<' ';
    return 0;
}