最小唯一前缀

#include<iostream>
(720)#include<vector>
#include<string>
using namespace std;
class trie_node{
public:
    int cnt;
    trie_node* next[26];
    trie_node(){
        cnt=1;
        for(int i=0;i<26;i++){
            next[i]=nullptr;
        }
    }
};
int main(){
    trie_node* root=new trie_node();
    int n=0;
    cin>>n;
    vector<string> strs(n);
    for(int i=0;i<n;i++){
        string tmp;
        cin>>tmp;
        strs[i]=tmp;
        trie_node* p=root;
        for(int j=0;j<tmp.length();j++){
            if(p->next[tmp[j]-'a']!=nullptr){
                p->next[tmp[j]-'a']->cnt++;
            }
            else{
                p->next[tmp[j]-'a']=new trie_node();
            }
            p=p->next[tmp[j]-'a'];
        }
    }
    for(int i=0;i<n;i++){
        trie_node* p=root;
        int j=0;
        for(;j<strs[i].length();j++){
            if(p->next[strs[i][j]-'a']->cnt == 1){
                cout<<strs[i].substr(0,j+1)<<endl;
                break;
            }
            p=p->next[strs[i][j]-'a'];
        }
        if(j==strs[i].length()){
            cout<<strs[i]<<endl;
        }
    }
    return 0;
}

trie树

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
int son[N][26], cnt[N], idx;
int n;

void insert(string &str){
    int p = 0;
    for (int i = 0; str[i]; i++){
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        // 计算每个字符出现的次数
        cnt[son[p][u]]++;
        p = son[p][u];
    }

}

string query(string &str){
    int p = 0;
    for (int i = 0; str[i]; i++){
        int u = str[i] - 'a';
        // 出现次数为1的字符为终点的字符串为最小前缀
        if (cnt[son[p][u]] == 1) return str.substr(0, i + 1);
        p = son[p][u];
    }
    return str;
}

int main(){

    cin >> n;
    vector strs;
    while (n--) {
        string str;
        cin >> str;
        insert(str);
        strs.push_back(str);
    }

    for (auto && x : strs){
        cout << query(x) << endl;
    }

    return 0;
}

#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <string.h>
#include <memory>

using namespace std;

class Trie
{

public:
    struct Node
    {
        map<char, shared_ptr<Node>> subs;
        int cnt;

        Node()
        {
            cnt = 1;
        }
    };

    typedef map<char, shared_ptr<Node>>::iterator SubsIter;

    Trie()
    {
        root = make_shared<Node>();
    }
    void build(const string &str)
    {
        shared_ptr<Node> tmp = root;
        int len = str.length();
        SubsIter iter;
        for (int idx = 0; idx < len; ++idx)
        {
            iter = tmp->subs.find(str[idx]);
            if (iter == tmp->subs.end())
            {
                shared_ptr<Node> new_node = make_shared<Node>();
                tmp->subs.insert(make_pair(str[idx], new_node));
            }else{
                ++iter->second->cnt;
            }
            tmp = tmp->subs[str[idx]];
        }
    }
    string min_pre(const string &str)
    {
        shared_ptr<Node> tmp = root;
        int len = str.length();
        SubsIter iter;
        for (int idx = 0; idx < len; ++idx)
        {
            iter = tmp->subs.find(str[idx]);
            if (iter == tmp->subs.end())
            {
                return "";
            }
            if (iter->second->cnt == 1)
            {
                return str.substr(0, idx + 1);
            }
            tmp = iter->second;
        }
        return str;
    }

private:
    shared_ptr<Node> root;
};

int main()
{
    int n;
    cin >> n;
    vector<string> cell(n);
    Trie tree;
    for (int idx = 0; idx < n; ++idx)
    {
        cin >> cell[idx];
        tree.build(cell[idx]);
    }

    for(int idx = 0; idx < n; ++ idx)
    {
        cout<<tree.min_pre(cell[idx])<<endl;
    }

    return 0;
}

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
class Node {
public:
    int count = 1;
    unordered_map<char, Node*> child;
};
int main()
{
    int n;
    cin >> n;
    vector<string> strs(n);
    auto root = new Node();
    for (int i = 0; i < n; i++)
    {
        string input;
        cin >> input;
        strs[i] = input;
        auto ptr = root;
        for (int j = 0; j < input.size(); j++) {
            if (ptr->child.find(input[j]) == ptr->child.end()) {
                ptr->child.insert({ input[j],new Node() });
            }
            else
                ptr->child[input[j]]->count++;
            ptr = ptr->child[input[j]];
        }
    }
    for (int i = 0; i < n; i++) {
        auto ptr = root;
        int j = 0;
        while (j < strs[i].size() && ptr->child[strs[i][j]]->count != 1)
        {
            ptr = ptr->child[strs[i][j++]];
        }
        cout << strs[i].substr(0, j + 1) << endl;
    }
}

def commonSubingString(s, t):
    if s == t:
        return 0
    n = 0
    for ss, tt in zip(s, t):
        if ss == tt:
            n += 1
        else:
            break
    return n
 
 
if __name__ == '__main__':
    n = int(input())
    data = []
    for i in range(n):
        data.append(input())
    for d in data:
        r = max([commonSubingString(d, t) for t in data])
        print(d[:min(r + 1, len(d))])

import java.util.*;

public class Main {
        public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.valueOf(sc.nextLine());

        List<MyC> strs = new ArrayList<>();
        String[] ans = new String[n];
        
        for (int i = 0; i < n; i++) {
            strs.add(new MyC(sc.nextLine(), i));
            if(strs.get(i).s.length() == 0) {
                ans[i] = "";
            }
        }
        if (n == 1) {
            System.out.println(strs.get(0).s.substring(0, 1));
        } else {
            dfs(strs, 0, ans);
            for (String w : ans) {
                System.out.println(w);
            }
        }
        
    }


    private static void dfs(List<MyC> list, int cur_idx, String[] ans) {
        if (list == null || list.size() == 0) {
            return ;
        }
        if (list.size() == 1) {
            MyC w = list.get(0);
            ans[w.idx] = w.s.substring(0, cur_idx);
            return;
        }
        List<MyC>[] rec = new ArrayList[128];
        for (int i = 0; i < 128; i++) {
            rec[i] = new ArrayList<>();
        }
        for (MyC myC : list) {
            if (myC.s.length() == cur_idx) {
                ans[myC.idx] = myC.s;
            } else {
                rec[myC.s.charAt(cur_idx)].add(myC);
            }
        }
        for (List<MyC> myCS : rec) {
            dfs(myCS, cur_idx + 1, ans);
        }
    }
}


class MyC {
    String s;
    int idx;
    MyC (String s, int idx) {
        this.s = s;
        this.idx = idx;
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=Integer.valueOf(scan.nextLine());
        String ss[]=new String[n];
        for(int i=0;i<n;i++){
            ss[i]=scan.nextLine();
        }
        String s1[]=new String[n];
        for(int i=0;i<n;i++){
            int t=0;
            boolean flage=true;
            while(flage==true){
                flage=false;
                for(int j=0;j<i;j++){
                    if(ss[j].length()>t)
                        if(ss[j].charAt(t)==ss[i].charAt(t))
                            flage=true;
                }
                for(int j=i+1;j<n;j++){
                    if(ss[j].length()>t)
                        if(ss[j].charAt(t)==ss[i].charAt(t))
                            flage=true;
                }
                t++;
                if(t>=ss[i].length())
                    flage=false;
            }
            s1[i]=ss[i].substring(0,t);

        }
        for(int i=0;i<n;i++){
            System.out.println(s1[i]);
        }

    }
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        minPrefix();
    }
 
    private static void minPrefix() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String[] strs = new String[n];
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            strs[i] = scanner.next();
            maxLen = Math.max(maxLen, strs[i].length());
        }
 
        int[] minLen = new int[n]; // minLen[i]: strs[i]的最小前缀长度
 
        for (int i = 1; i <= maxLen; i++) {
            Map<String, Integer> map = new HashMap<>();
            for (int j = 0; j < n; j++) {
                if(minLen[j] != 0)
                    continue;
                if(i == strs[j].length()) {
                    minLen[j] = i;
                }
                String str = strs[j].substring(0, i);
                map.put(str, map.getOrDefault(str, 0) + 1);
            }
 
            for(int j = 0; j < n; j++){
                if(minLen[j] != 0)
                    continue;
 
                String str = strs[j].substring(0, i);
                if(map.get(str) == 1)
                    minLen[j] = i;
            }
        }
        for(int i = 0; i < n; i++){
            System.out.println(strs[i].substring(0, minLen[i]));
        }
    }
}

#include<iostream>
(720)#include<string>
#include<vector>
(721)#include<algorithm>
#include<unordered_map>
 
using namespace std;
 
int main(){
    int N;
    cin>>N;
    vector<string> vec;
    string temp;
    size_t max_len=0; // 所有字符串最大长度
    for(int i=0;i<N;i++){
        cin>>temp;
        max_len=max(max_len, temp.size());
        vec.push_back(temp);
    }
    vector<int> pre_len(vec.size(),0); // 所有字符串前缀长度，初始为0
    // 遍历前缀长度
    for(int i=1;i<=max_len;i++){
        // 若前缀长度为i，将所有字符串的前缀统计个数
        unordered_map<string, int> map;
        for(int j=0;j<vec.size();j++){
            if(pre_len[j]>0) continue;
            string pre=vec[j].substr(0,i);
            if(map.find(pre)==map.end()){
                map[pre]=1;
            }else{
                map[pre]++;
            }
        }
        
        // 前缀个数为1的，可以作为其最终的前缀结果
        for(int j=0;j<vec.size();j++){
            if(pre_len[j]>0) continue;
            string pre=vec[j].substr(0,i);
            if(map[pre]==1) pre_len[j]=i;
        }
    }
     
    for(int i=0;i<pre_len.size();i++){
        cout<<vec[i].substr(0,pre_len[i])<<endl;
    }
    return 0;
}

//前缀树
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        sc.nextLine();
        String[] strArr=new String[n];
        PrefixTree tree=new PrefixTree();
        for(int i=0;i<n;i++){
            strArr[i]=sc.nextLine();
            tree.insert(strArr[i]);
        }
        for(String s:strArr)
            System.out.println(tree.findMaxPrefix(s));
    }
    public static class TreeNode{
        public int path;
        public int end;
        public HashMap<Character,TreeNode> map;
        public TreeNode(){
            path=0;
            end=0;
            map=new HashMap<Character,TreeNode>();
        }
    }
    public static class PrefixTree{
        private TreeNode root;
        public PrefixTree(){
            root=new TreeNode();
        }
        public void insert(String word){
            if(word==null)
                return;
            char[]chs=word.toCharArray();
            TreeNode node=root;
            for(int i=0;i<chs.length;i++){
                if(!node.map.containsKey(chs[i]))
                    node.map.put(chs[i],new TreeNode());
                node=node.map.get(chs[i]);
                node.path++;
            }
            node.end++;
        }
        public String findMaxPrefix(String word){
            if(word.isEmpty())
                return "";
            TreeNode node=root;
            String res="";
            char[]chs=word.toCharArray();
            for(int i=0;i<chs.length;i++){
              if(node.map.containsKey(chs[i])){
                  node=node.map.get(chs[i]);
                  res+=chs[i];
                  if(node.path==1)
                      return res;
              }else
                  return "";
            }
            return res;
        }
    }
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        scanner.nextLine();
        String[] strings = new String[num];
        for(int i=0; i<num; ++i){
            strings[i] = scanner.nextLine();
        }
        scanner.close();
        TreeNode treeNode = new TreeNode();
        for(int i=0; i<num; ++i){
            treeNode.insert(strings[i]);
        }
        for(int i=0; i<num; ++i){
            treeNode.prefix(strings[i]);
        }
    }

    static class TreeNode{

        private int path;
        private boolean isWord;
        private Map<Character, TreeNode> next;

        public TreeNode(){
            path = 0;
            next = new HashMap<Character, TreeNode>();
            isWord = false;
        }

        public void insert(String s){
            TreeNode curr = this;
            for(int i=0; i<s.length(); ++i){
                char c = s.charAt(i);
                ++curr.path;
                if(curr.next.containsKey(c)){
                    curr = curr.next.get(c);
                }else {
                    curr.next.put(c, new TreeNode());
                    curr = curr.next.get(c);
                }
            }
            curr.isWord = true;
        }

        public void prefix(String s){
            TreeNode curr = this;
            for(int i=0; i<s.length(); ++i){
                if(curr.next.get(s.charAt(i)).isWord){
                    if(i==(s.length()-1)){
                        System.out.println(s.substring(0,i+1));
                        break;
                    }else {
                        curr = curr.next.get(s.charAt(i));
                    }
                }else{
                    if(curr.next.get(s.charAt(i)).path==1){
                        System.out.println(s.substring(0,i+1));
                        break;
                    }
                    curr = curr.next.get(s.charAt(i));
                }
            }
        }
    }
}

import java.util.*;
public class Main{
    public static String iskmp(String a,String b){
       int n = (a.length()>=b.length())? b.length() : a.length();
    for(int i=0;i<n;i++){
      if(a.charAt(i)!=b.charAt(i)){
        return a.substring(0,i);
      }
    }
    return (a.length()>=b.length())? b : a;
    }
    public static void main(String[] args){
       Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    List<String> strs = new ArrayList<>();
    for(int i=0;i<n;i++){
      String ne = in.next();
      strs.add(ne);
    }
    String[] result = new String[n];
    for(int i=0;i<strs.size();i++){
      int max=0;
          for(int j=0;j<strs.size();j++){
            if(i==j){
              continue;
            }
            int now = iskmp(strs.get(i),strs.get(j)).length();
            if(now>max){
              max = now;
            }
          }
          if(strs.get(i).length()==max){
            result[i]=strs.get(i);
          }
          else {
            result[i] = strs.get(i).substring(0, max + 1);
          }
    }
    for(int i=0;i<n;i++){
      System.out.println(result[i]);
    }
    }
}