Cod sursa(job #2458143)

Utilizator ViAlexVisan Alexandru ViAlex Data 19 septembrie 2019 19:15:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int z[4000010];

void zz(string a)
{
    int l=0;
    int r=0;
    z[0]=a.length();
    for(int k=1; k<a.length(); k++)
    {
        if(k>r)
        {
            r=k;
            l=k;

            while(a[r]==a[r-l])
            {
                r++;
            }
            z[k]=r-l;
            r--;
        }
        else
        {
            if(z[k-l]<r-k+1)
            {
                z[k]=z[k-l];
            }
            else
            {
                l=k;
                while(a[r]==a[r-l])
                {
                    r++;
                }
                z[k]=r-l;
                r--;

            }

        }
    }

}


void srch(string text,string pattern)
{
    string res=pattern+text;
    vector<int>results;
    zz(res);
    for(int i=1; i<res.length(); i++)
    {
        if(i>=pattern.length() && z[i]>=pattern.length())
        {
            results.push_back(i-pattern.length());
        }
    }
    int index=results.size();
    out<<index<<endl;
    index=min(index,1000);
    for(int i=0; i<index; i++)
        out<<results[i]<<" ";
}


int main()
{
    string a,b;
    in>>a>>b;
    srch(b,a);
    return 0;
}