Cod sursa(job #2476523)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 19 octombrie 2019 01:09:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;

string s1,s2;

int z[4000010];

void calcz(string s)
{
    int len=s.length();
 //   cout<<len<<'\n';
    int i,left,right;
    left=right=0;
    for(i=1;i<len;i++)
    {
   //     cout<<i<<'\n';
        if(i>right)
        {
            left=right=i;
            while(s[right]==s[right-left] && right<len)
                right++;
            z[i]=right-left;
            right--;
        }
        else
        {
            if( z[i-left]< right-i+1)
                z[i]=z[i-left];
            else
            {
                left=i;
                while(s[right]==s[right-left] && right<len)
                    right++;
                z[i]=right-left;
                right--;
            }
        }
    }
}

int main()
{
    ifstream t1("strmatch.in");
    ofstream t2("strmatch.out");
    t1>>s1>>s2;
    string aux=s1+"~"+s2;
    int len=s1.length();
    calcz(aux);
    int sol=0,i;
    queue<int> q;
    for(i=len+1;i<aux.length();i++)
        if(z[i]==len)
        {
            sol++;
            q.push(i-len-1);
        }
    t2<<sol<<'\n';
    int nr=0;
    while(!q.empty())
    {
        nr++;
        if(nr==1001) break;
        t2<<q.front()<<' ';
        q.pop();
    }
    t1.close();
    t2.close();
    return 0;
}