Cod sursa(job #2654777)

Utilizator tudorbuhniaTudor Buhnia tudorbuhnia Data 2 octombrie 2020 11:43:21
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <stack>
using namespace std;
string zero=" ";
int pi[2000005],s[1005];
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    int k,la,lb,l=0,cnt=0,res=0;
    string a,b;
    cin >> a;
    cin >> b;
    la=a.size();
    lb=b.size();
    a=zero+a;
    a+=zero;
    b=zero+b;
    for(int i=2;i<=la;i++)
    {
        if(a[i]==a[l+1])
            l++;
        else
        {
            while(l>0 && a[l]!=a[i])
                l=pi[l-1];
        }
        pi[i]=l;
    }
    l=0;
    for(int i=1;i<=lb;i++)
    {
        if(b[i]==a[l+1])
        {
            l++;
            if(l==la)
            {
                if(cnt<1000)
                {
                    s[cnt]=i-la;
                    cnt++;
                }
                res++;
                l--;
            }
        }
        else
        {
            while(l>0 && a[l+1]!=b[i])
            {
                l=pi[l-1];
            }

        }
    }
    cout << res << '\n';
    for(int i=0;i<cnt;i++)
        cout << s[i] << " ";
    return 0;
}