Cod sursa(job #2550597)

Utilizator MihclerioVladimir Chim Mihclerio Data 18 februarie 2020 21:39:34
Problema Potrivirea sirurilor Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std;

int pr[100];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    string a,b;
    cin>>a>>b;
    string aux(1,'#');
    string s=a+aux+b;
    int ans=0;
    vector<int>v;
    pr[0]=-1;
    for(int i=1;i<=s.size();i++)
    {
        int k=pr[i-1];
        while(k>=0)
        {
            if(s[k]==s[i-1])
            {
                pr[i]=k+1;
                if(pr[i]==a.size()) ans++,v.push_back(i-a.size()*2-1);
                break;
            }
            k=pr[k];
        }
    }
    cout<<ans<<"\n";
    for(auto it:v) cout<<it<<" ";

}