Cod sursa(job #2461699)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 25 septembrie 2019 23:11:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include<fstream>
#include<iostream>
#include<vector>
using namespace std;

string a,b,concat;
int z[4000010];

int main()
{
    ifstream t1("strmatch.in");
    ofstream t2("strmatch.out");
    t1>>a;
    t1>>b;
    concat=a+'!'+b;
    cout<<concat<<'\n';
    int len=a.length();
    int i,l,r;
    l=r=0;
    int sol=0;
    vector<int> poz;
    for(i=1;i<concat.length();i++)
    {
        if(i>r)
        {
            l=r=i;
            while(r<concat.length() && concat[r]==concat[r-l])
                r++;
            z[i]=r-l;
            r--;
        }
        else
        {
            int k=i-l;
            if( z[k] <r-i+1)
            {
                z[i]=z[k];
            }
            else
            {
                l=i;
                while(r<concat.length() && concat[r]==concat[r-l])
                    r++;
                z[i]=r-l;
                r--;
            }
        }

        if(z[i]==len)
        {
            sol++;
            poz.push_back(i-len-1);
        }
    }
   /* for(i=0;i<concat.length();i++)
        cout<<concat[i]<<' '; cout<<'\n';
    for(i=0;i<concat.length();i++)
        cout<<z[i]<<' '; cout<<'\n';*/
    t2<<sol<<'\n';
    for(auto it:poz)
        t2<<it<<' '; t2<<'\n';
    t1.close();
    t2.close();
    return 0;
}