Cod sursa(job #3163450)

Utilizator laura2020Moldovan Laura laura2020 Data 31 octombrie 2023 14:42:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> pi,q;

int main()
{
    string s1,s;
    fin>>s1>>s;
    s=s1+'?'+s;
    pi.resize(s.size());
    pi[0]=0;
    int k=0,i;
    for(i=1;i<s.size();i++)
    {
        while(k && s[k]!=s[i])
            k=pi[k-1];
        if(s[k]==s[i])
            k++;
        pi[i]=k;
        if(pi[i]==s1.size() && i>=2*s1.size())
        {
            q.push_back(i-2*s1.size());
        }
    }
    fout<<q.size()<<'\n';
    for(i=0;i<q.size() && i<1000;i++)
        fout<<q[i]<<" ";
    return 0;
}