Cod sursa(job #2866810)

Utilizator adiaioanaAdia R. adiaioana Data 9 martie 2022 23:33:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string A,B,aux,aux1;
int pre[2000200];
vector <int> sol;

inline void scan(); ///
int main()
{
    scan();
    if(A.size()>B.size())
    {
        cout<<0<<'\n';
        return 0;
    }

    int q=0, cnt=0;
    for(int i=2; i<A.size(); ++i)
    {
        while(q && A[q+1]!=A[i])
            q=pre[q];
        if(A[q+1]==A[i])
            q++;
        pre[i]=q;
    }

    q=0;
    for(int i=1; i<B.size(); ++i)
    {
        while(q && A[q+1]!=B[i])
            q=pre[q];
        if(B[i]==A[q+1])
            q++;
        if(q+1==A.size())
            sol.push_back(i-q);
    }

    cout<<sol.size()<<'\n';
    for(auto it:sol)
    {
        cout<<it<<' '; cnt++;
        if(cnt>999) break;
    }
    cout<<'\n';
    return 0;
}

inline void scan()
{
    cin>>aux;
    A="0";B="0";
    A.append(aux);
    cin>>aux1;
    B.append(aux1);
}