題目描述：

2110年美團外賣火星第3000號配送站點有26名騎手调窍，分別以大寫字母A-Z命名猬仁，因此可以稱呼這些騎手為黃家騎士特工A，黃家騎士特工B…黃家騎士特工Z先誉，某美團黑珍珠餐廳的外賣流水線上會順序產(chǎn)出一組包裹诈闺，美團配送調(diào)度引擎已經(jīng)將包裹分配到騎手，并在包裹上粘貼好騎手名稱仁烹，如RETTEBTAE代表一組流水線包裹共9個，同時分配給了名字為A B E R T的5名騎手征唬。請在不打亂流水線產(chǎn)出順序的情況下扶歪，把這組包裹劃分為盡可能多的片段，同一個騎手只會出現(xiàn)在其中的一個片段炫欺，返回一個表示每個包裹片段的長度的列表囱怕。

輸入

輸入數(shù)據(jù)只有一行典格，為一個字符串(不包含引號)，長度不超過1000防嗡，只包含大寫字母'A'到'Z'，字符之間無空格。

輸出

輸出每個分割成片段的包裹組的長度钢属，每個長度之間通過空格隔開

樣例輸入

MPMPCPMCMDEFEGDEHINHKLIN

樣例輸出

9 7 8

代碼：

#include <iostream>
#include <vector>
using namespace std;

int divide(string S, int start, int end,int letterRight[26])
{
    int left, right;
    left = start;
    right = letterRight[S[left] - 'A'];
    for (int i = left+1; i <= right; i++)
    {
        if (letterRight[S[i]-'A'] > right) right = letterRight[S[i] - 'A'];
    }
    return right - left+1;
 
}
 
vector<int> partitionLabels(string S) {
    int letterRight[26];
    vector<int> result;
 
    for (int i = 0; i < 26; i++)
    {
        int t = S.find_last_of((char)( i + 'A'));
        letterRight[i] = t;
    }
    int start = 0; int end = S.size(); int tmp;
    while (start < end)
    {
        tmp = divide(S, start, end, letterRight);
        result.push_back(tmp);
        start += tmp;
    }
    return result;
}
int main(){
    string str;
    getline(cin, str);
    vector<int> result = partitionLabels(str);
    for (int i=0; i<result.size(); i++){
        cout<<result[i]<<" ";
    }
    return 0;
} 

題目描述：

給定一組個字符串窒升，為每個字符串找出能夠唯一識別該字符串的最小前綴。

輸入

輸入n串唯一的字符串，n為2到100之間酪呻，字符串用“,”隔開贼邓，字符串長度不超過100女坑。

輸出

可以唯一區(qū)分字符串的最小前綴誉简，用“,”隔開。

樣例輸入

meituanapp,meituanwaimai,dianpingliren,dianpingjiehun

樣例輸出

meituana,meituanw,dianpingl,dianpingj

代碼

#include<stdio.h>
#include <iostream>
#include<string.h>
#include <string>
#define N 2501

using namespace std;
int trie[N][105]; 
int trie_flag[N]; 
int tot=0;
void insert(char *s){
    int i,id,len,root=0; 
    len=strlen(s);
    for(i=0;i<len;i++)
    {   
        id=s[i]-'a';
        if(!trie[root][id]) trie[root][id]=++tot;
        trie_flag[trie[root][id]]++;
        root=trie[root][id];
   }
}
void search(char *s){
    //printf("%s ",s);
    int i,len,id,root=0;
    len=strlen(s);
    for(i=0;i<len;i++)
    {    
        printf("%c",s[i]);
        id=s[i]-'a';
        if(trie_flag[trie[root][id]]==1)break;
           root=trie[root][id];
    }
}
int main()
{   
    char s[105][105];
    int n=0; 
    memset(trie,0,sizeof(trie));
    memset(trie_flag,0,sizeof(trie_flag));
    string str;
    getline(cin, str);
    int j = 0;
    for (int k=0; k<str.size(); k++){
        if (str[k] != ','){
            s[n][j++] = str[k];
        }else{
            j = 0;
            insert(s[n++]);
        }
    }
    insert(s[n++]);
    int i=0;
    while(n--) {
        search(s[i++]); 
        if(n != 0)cout<<","; 
    } 
    return 0;   
}