Twosigma在线笔试 substring，twosigmasubstring

Twosigma在线笔试 substring，twosigmasubstring

题意

给你一个字符串，让你找出这个字符串以元音字母开头（a，e，i，o，u），辅音字母结尾的所有子串，中的字典序最大串和最小串。

思路

虽然是面试题，但是我觉得这是我见过的最难的面试题

暴力解

#include<iostream>
#include<unordered_set>
#include<string>

using namespace std;



int main(int argc, char const *argv[])
{
    unordered_set<char> st;
    st.insert('a');
    st.insert('e');
    st.insert('i');
    st.insert('o');
    st.insert('u');

    string minString = "", maxString = "";
    int index[2] = {-1, -1};
    string s = "abcdeuudeaeauuzaaa";
    for(int i = s.length() - 1; i >= 0; i--) 
    {
        if(st.count(s[i]) == 0) 
        {
            if(index[0] == -1)
                index[1] = i;
            index[0] = i;
        } 
        else 
        {
            if(index[0] == -1)
                continue;
            string a = s.substr(i, index[0] + 1 - i);
            string b = s.substr(i, index[1] + 1 - i);
            if(minString.length() == 0) 
            {
                minString = a;
                maxString = b;
            } 
            else 
            {
                if(minString > a)
                    minString = a;
                if(maxString < b)
                    maxString = b;
            }
        }
    }
    cout<<minString<<endl;
    cout<<maxString<<endl;
    return 0;
}

后缀数组

直接无脑后缀数组
时间复杂度$O\left(nlogn\right)$

#include<iostream>
#include<unordered_set>
#include<string>
#include<vector>

using namespace std;

const int MAXN = 500001;

int t1[MAXN],t2[MAXN],c[MAXN];
int sa[MAXN], num[MAXN];

bool cmp(int r[], int a, int b, int l) {
    return r[a] == r[b] && r[a+l] == r[b+l];
}

void build_sa(int s[], int n, int m)
{
    int i,j,p,*x=t1,*y=t2;
    //第一轮基数排序，如果s的最大值很大，可改为快速排序
    for(i=0;i<m;i++)c[i]=0;
    for(i=0;i<n;i++)c[x[i]=s[i]]++;
    for(i=1;i<m;i++)c[i]+=c[i-1];
    for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    for(j=1;j<=n;j<<=1)
    {
        p=0;
        //直接利用sa数组排序第二关键字
        for(i=n-j;i<n;i++)y[p++]=i;//后面的j个数第二关键字为空的最小
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        //这样数组y保存的就是按照第二关键字排序的结果
        //基数排序第一关键字
        for(i=0;i<m;i++)c[i]=0;
        for(i=0;i<n;i++)c[x[y[i]]]++;
        for(i=1;i<m;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
        //根据sa和x数组计算新的x数组
        swap(x,y);
        p=1;x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
        if(p>=n)break;
        m=p;//下次基数排序的最大值
    }
}

int main()
{
    string str = "abcdeuudeaeauuzaaa";
    unordered_set<char> st;
    st.insert('a');
    st.insert('e');
    st.insert('i');
    st.insert('o');
    st.insert('u');

    int n = str.length();
    for(int i = 0; i < n; i++)
        num[i] = str[i] - 'a';
    
    vector<int> sum(n+1, 0);

    for(int i = n-1; i >= 0; i--)
        if(st.find(str[i]) == st.end())
            sum[i] = sum[i+1] + 1;
        else
            sum[i] = sum[i+1];

    build_sa(num, n, 26);

    string smin = "";
    string smax = "";

    for(int i = 0; i < n; i++)
    {
        bool flag = false;
        int ansr = 0;
        if(st.find(str[sa[i]]) != st.end() && sum[sa[i]] > 0)
        {
            for(int j = sa[j]+1; j < n; j++)
            {
                if(st.find(str[j]) == st.end())
                {
                    ansr = j;
                    flag = true;
                    break;
                }
            }
        }
        if(flag)
        {
            for(int j = sa[i]; j <= ansr; j++)
                smin += string(1, str[j]);
            break;
        }
    }
    for(int i = n-1; i >= 0; i--)
    {
        bool flag = false;
        int ansr = 0;
        if(st.find(str[sa[i]]) != st.end() && sum[sa[i]] > 0)
        {
            for(int j = n-1; j > sa[i]; j--)
            {
                if(st.find(str[j]) == st.end())
                {
                    ansr = j;
                    flag = true;
                    break;
                }
            }
        }
        if(flag)
        {
            for(int j = sa[i]; j <= ansr; j++)
                smax += string(1, str[j]);
            break;
        }
    }
    cout<<smin<<endl;
    cout<<smax<<endl;
    return 0;
}