Cod sursa(job #2447421)

Utilizator miguelMihail Lavric miguel Data 13 august 2019 12:38:29
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.83 kb
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define pii pair<pair <int, int>, int>
#define vi vector <int>
const ll mod = 1000000007;
const ll nmax=1000003;
#define int ll
string s, t;
int xd;

vi pref(string s){
    int n=s.size();
    vi v;
    vi ans;
    v.resize(n);
    v[0]=0;
    for(int i=1; i<n; i++){
        int x=v[i-1];
        while(x>0 && s[i]!=s[x]) x=v[x-1];
        if(s[i]==s[x]) x++;
        v[i]=x;
        if(i>xd && v[i]==xd){
            ans.pb(i-2*xd);
            if(ans.size()>=1000) return ans;
        }
    }
    return ans;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>s>>t;
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    xd=s.size();
    s=s+"#"+t;
    vi v=pref(s);
    cout<<v.size()<<"\n";
    for(int i: v) cout<<i<<" ";
}