Twosigma在线笔试 substring

淩亂°似流年 2022-05-11 03:58 113阅读 0赞

## 题意 ##

给你一个字符串，让你找出这个字符串以元音字母开头（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 ( n l o g n ) O(nlogn) O(nlogn)

#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;
    }