Cod sursa(job #3249842)

Utilizator vlad7654vladimir manescu vlad7654 Data 18 octombrie 2024 11:02:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i=1;i<n; i++) {
        int j=pi[i-1];
        while(j>0 and s[i] != s[j]){
            j=pi[j-1];
        }
        if(s[i] == s[j]){
            j++;
        }
        pi[i]=j;
    }
    return pi;
}
vector<int> z_function(string s) {
    int n = s.size();
    vector<int> z(n);
    int l=0, r=0;
    for(int i=1;i<n;i++) {
        if(i<r){
            z[i]=min(r-i,z[i-l]);
        }
        while(i+z[i]<n and s[z[i]]==s[i+z[i]]) {
            z[i]++;
        }
        if(i+z[i]>r) {
            l=i;
            r=i+z[i];
        }
    }
    return z;
}
int main(){
    string a, b;
    fin>>a>>b;
    b=a+'#'+b;
    vector<int> z=z_function(b), ans1;
    int ans=0;
    for(int i=1;i<=a.size()+b.size()-1;i++){
        if(z[i]==a.size()){
            ans++;
            if(ans1.size()<1000){
                ans1.push_back(i-a.size()-1);
            }
        }
    }
    fout<<ans<<'\n';
    for(int i:ans1){
        fout<<i<<' ';
    }
}