Cod sursa(job #2641146)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 10 august 2020 12:15:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,sa[30][100005];
string s;
int LCP(int i, int j)
{
    int ans=0;
    int m=n-max(i,j)+1;
    int p=0;
    while((1<<(p+1))<=m)
    {
        p++;
    }
    for(; p>=0; p--)
    {
        if(sa[p][i]==sa[p][j])
        {
            ans+=(1<<p);
            i+=(1<<p);
            j+=(1<<p);
        }
    }
    return ans;
}
int main()
{
    vector<int> rez;
    string a,b;
    getline(f,a);
    getline(f,b);
    s='#'+a+'#'+b;
    n=s.size()-1;
    vector<pair<pair<int,int>,int>> key(200005);
    for(int i=1; i<=n; i++)
    {
        key[i]= {{s[i],s[i]},i};
    }
    sort(key.begin()+1,key.begin()+n+1);
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(key[i].first!=key[i-1].first)
        {
            ++cnt;
        }
        sa[0][key[i].second]=cnt;
    }
    for(int i=1; (1<<(i-1))<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            key[j]= {{sa[i-1][j],sa[i-1][j+(1<<(i-1))]},j};
            pair<pair<int,int>,int> k=key[j];
            int nmmmmmm=0;
        }
        sort(key.begin()+1,key.begin()+n+1);
        cnt=0;
        for(int j=1; j<=n; j++)
        {
            if(key[j].first!=key[j-1].first)
            {
                ++cnt;
            }
            sa[i][key[j].second]=cnt;
        }
    }
    for(int i=a.size()+2; i<=n; i++)
    {
        if(LCP(1,i)>=a.size())
        {
            rez.push_back(i-a.size()-2);
        }
    }
    g<<rez.size()<<'\n';
    cnt=0;
    for(auto it : rez)
    {
        ++cnt;
        if(cnt>1000)
        {
            return 0;
        }
        g<<it<<' ';
    }
    return 0;
}