Cod sursa(job #2465418)

Utilizator RadianElevenAdrian Ariotn RadianEleven Data 30 septembrie 2019 09:25:13
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int z[2000004];
int r,l;
string s1, s2;
void findin(string c, string st)
{
    string s=c+"*"+st+"$";
    int t;
    z[1]=0;
    int n=s.size();
    int k=2;
    for(k=2;k<s.size();++k)
    {
        if(k>r)
        {
            l=r=k;

            while(r<n && s[r-l] == s[r])
                r++;
            z[k]=r-l;
            r=r-1;
        } else {
           t=k-l;
           if(z[t] < r-k+1)
                z[k]=z[t];
           else {
               l=k;
               while(s[r] == s[r-l] && r<n)
                r++;
                 z[k]=r-l;
                r=r-1;
           }
        }
    }

    int m=c.size();
    int mys=0;
    for(int i=m+1;i<=st.size()+m+1;++i)
    {

        if(z[i]==c.size())
            mys++;
    }
    g<<mys<<"\n";
    for(int i=m+1;i<=st.size()+m+1;++i)
    {

        if(z[i]==c.size())
            g<<i-m-1<<" ";
    }
}
int main()
{

    f>>s1>>s2;
    findin(s1,s2);
    return 0;
}