Cod sursa(job #2465419)

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

            while(r<n && s[r-l] == s[r])
                r++;
            z[k]=r-l;
            r--;
        } 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;
           }
        }
    }

    long long unsigned m=c.size();
   long long unsigned mys=0;
    for(long long unsigned i=m+1;i<=s.length();++i)
    {

        if(z[i]==c.length())
            mys++;
    }
    g<<mys<<"\n";
    for(long long unsigned i=m+1;i<=s.length();++i)
    {

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

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