最短前缀

// write your code here
import java.util.Scanner;
import java.util.Comparator;
import java.util.Arrays;
class Str{
    int id;
    String str;
}
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            int n=in.nextInt();
            Str[] sa=new Str[n];
            for(int i=0;i<n;i++){
                sa[i]=new Str();
                sa[i].id=i;
                sa[i].str=in.next();
            }
            Arrays.sort(sa,new Comparator<Str>(){
                public int compare(Str s1,Str s2){
                    return s1.str.compareTo(s2.str);
                }
            });
            for(int i=0;i<n;i++){
                int j=0;
                if(i-1>=0)
                    for(;j<sa[i].str.length() && j<sa[i-1].str.length();j++)
                        if(sa[i-1].str.charAt(j)!=sa[i].str.charAt(j))
                            break;
                int k=0;
                if(i+1<n)
                    for(;k<sa[i].str.length() && k<sa[i+1].str.length();k++)
                        if(sa[i+1].str.charAt(k)!=sa[i].str.charAt(k))
                            break;
                if(k>j) j=k;
                if(j==sa[i].str.length()) j--;
                sa[i].str=sa[i].str.substring(0,j+1);
            }
            Arrays.sort(sa,new Comparator<Str>(){
                public int compare(Str s1,Str s2){
                    return s1.id-s2.id;
                }
            });
            for(int i=0;i<n;i++) System.out.println(sa[i].str);
            System.out.println();
        }
        in.close();
    }
}

字典树
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <memory>
#include <sstream>
#include <functional>

using namespace std;

struct Trie 
{
 char _c;
 int _count;
 unordered_map<char, shared_ptr<Trie>> _next;
 Trie(){}
 Trie(char c) :_c(c),_count(0){}
};

int main()
{
 //freopen("in.txt", "r", stdin);
 int n;
 while (cin >> n)
 {
  shared_ptr<Trie> root(new Trie);
  vector<string> words(n);
  for (int i = 0; i < n; ++i)
  {
   cin >> words[i];
   auto p = root;
   for (auto& c : words[i])
   {
    if (p->_next.find(c) == p->_next.end()) p->_next[c] = make_shared<Trie>(c);
    p = p->_next[c];
    ++p->_count;
   }
  }

  for (auto& s : words)
  {
   auto p = root;
   ostringstream os;
   for (auto& c : s)
   {
    p = p->_next[c];
    os << c;
    if (p->_count == 1) break;
   }
   cout << os.str() << endl;
  }
  cout << endl;
 }
 return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n=in.nextInt();
			String[] contArr=new String[n];
			int[] lenArr=new int[n];
			char[][] splitArr=new char[n][];
			int[] index=new int[n];
			for (int i = 0; i < n; i++) {
				index[i]=i;
			}
			for (int i = 0; i < n; i++) {
				String ts=in.next();
				int len=ts.length();
				contArr[i]=ts;
				lenArr[i]=len;
				splitArr[i]=ts.toCharArray();
			}
//			System.out.println(Arrays.deepToString(splitArr));
			
			int temp=0;
			char[] tempArr=new char[]{};
			for (int i = 0; i < n-1; i++) {
				for (int j = 0; j < n-1; j++) {
					if(lenArr[j]>lenArr[j+1]){
						tempArr=splitArr[j];
						splitArr[j]=splitArr[j+1];
						splitArr[j+1]=tempArr;
						
						temp=lenArr[j];
						lenArr[j]=lenArr[j+1];
						lenArr[j+1]=temp;
						
						temp=index[j];
						index[j]=index[j+1];
						index[j+1]=temp;
					}
				}
			}
//			System.out.println(Arrays.deepToString(splitArr));
			
			String[] rs=new String[n];
			for (int i = 0; i < n; i++) {
				int tlen=splitArr[i].length;
				for (int j = 0; j < tlen; j++) {
					char tc=splitArr[i][j];
					boolean flag=true;
					int count=0;
					for (int k = i+1; k < n; k++) {
						if(splitArr[k][j]==tc){
							count++;
						}
						else{
							flag=false;
						}
						
						if(!flag && count>0){
							break;
						}
					}
					if(count==n-(i+1)){
						if(j==tlen-1){
							rs[i]=String.valueOf(splitArr[i]);
						}
					}
					else if(count==0){
						rs[i]=String.valueOf(Arrays.copyOfRange(splitArr[i], 0, j+1));
						break;
					}
				}
			}
			
			//Last
			String last=rs[n-1];
			int lastIndex=-1,maxLen=Integer.MIN_VALUE;
			for (int i = 0; i < n-1; i++) {
				String tStr=rs[i];
				int len=tStr.length();
				if(last.startsWith(tStr.substring(0, len-1))){
					if(len>maxLen){
						maxLen=len;
						lastIndex=i;
					}
				}
			}
			rs[n-1]=rs[n-1].substring(0, maxLen);
			
			for (int i = 0; i < n; i++) {
				System.out.println(rs[index[i]]);
			}
//			System.out.println(Arrays.toString(rs));
            System.out.println();
		}
	}
}

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			String[] arr = new String[n];
			for (int i = 0; i < arr.length; i ++ ) {
				arr[i] = sc.next();
			}
			Trie root = createTrie(arr);
			String[] res = new String[n];
			for (int i = 0; i < res.length; i ++ ) {
				res[i] = prefix(root, arr[i]);
			}
			for (String s:res) {
				System.out.println(s);
			}
			System.out.println();
		}
	}

	public static Trie createTrie(String[] arr) {
		Trie root = new Trie('-');
		Trie cur;
		for (String s:arr) {
			cur = root;
			for (int i = 0; i < s.length(); i ++ ) {
				int position = s.charAt(i) - 'a';
				if(cur.next[position] == null) {
					cur.next[position] = new Trie(s.charAt(i));
				} else {
					cur.next[position].num ++ ;
				}
				cur = cur.next[position];
			}
		}
		return root;
	}

	public static String prefix(Trie root, String s) {
		String res = "";
		Trie cur;
		for (int i = 0; i < s.length(); i ++ ) {
			cur = root.next[s.charAt(i) - 'a'];
			if(cur == null) break;
			if(cur.num == 1) {
				res += s.charAt(i);
				break;
			} else {
				res += s.charAt(i);
				root = cur;
			}
		}
		return res;
	}

	static class Trie {
		private char name;
		private int num = 1;
		private Trie[] next = new Trie[26];

		public Trie(char name) {
			this.name = name;
		}
	}
}

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

struct Node
{
	char ch;						// 字典节存储一个字母
	int count = 1;					// 以此为前缀的单词总数
	bool isEnd = false;				// 是否为单词的终点
	Node * link[26] = {NULL};		// 指向下一节点的指针数组
};

// 创建字典树
Node * CreateTire(vector<string> & list)
{
	Node * root = new Node;			// 字典树根节点，不动
	Node * prev, * cur;				// prev前一节点，cur当前节点
	for (string str : list)			// 对每个string建立字典树中的路径
	{
		prev = root, cur = root;	// 初始化
		for (int i = 0; i < str.size(); ++i)
		{							// 对string中每个char通过遍历方式查找存储的节点
			if (prev->link[str[i] - 'a'] == NULL)
			{						// 对于当前字母，如果前一节点对应的指针为空
				cur = new Node;		// 那么就新建一个节点来存储这个字母
				cur->ch = str[i];	// 然后将前一节点和当前节点连接起来
				prev->link[str[i] - 'a'] = cur;
				prev = cur;
			}						// 否则说明已经有该路径，那么只要沿着路径进行遍历即可
			else
			{
				prev = prev->link[str[i] - 'a'];
				cur = prev;
				cur->count += 1;
			}
		}
		cur->isEnd = true;			// 遍历结束时，将最后一位字母对应的标记置为“号码结束”
	}
	return root;					// 返回字典根
}

// 计算所有单词的最短前缀，计算的标准为：
// 1、如果当前字母的count位为1，说明只有一个单词以此为前缀，即为当前单词的最短前缀
// 2、如果当前字母已经为单词的末位，而尚未发现count位为1的情况，那么整个单词为当前单词的最短前缀
vector<string> findPrefix(Node * root, vector<string> & list)
{
	vector<string> prefix;
	Node * cur;
	for (string str : list)					// 对每个单词进行判断
	{
		cur = root;							// 初始化
		for (int i = 0; i < str.size();++i)
		{									// 对每个字母进行判断
			cur = cur->link[str[i] - 'a'];	// 不断向下遍历
			if (cur->count == 1)			// 如果当前字母的count位为1，发现最短前缀
			{
				prefix.push_back(string(str.begin(), str.begin() + i + 1));
				break;						// 跳出，进行下一个单词的判断
			}
			else if (i == str.size() - 1)	// 如果当前字母已经为单词的末位，发现最短前缀
			{
				prefix.push_back(str);
				break;						// 跳出，进行下一个单词的判断
			}
		}
	}
	return prefix;							// 所有单词遍历完毕，返回单词前缀表
}

int main()
{
	int n;
	while (cin >> n && n)
	{
		vector<string> list(n);
		for (int i = 0; i < n; ++i) cin >> list[i];

		Node * root = CreateTire(list);
		vector<string> prefix = findPrefix(root, list);
		for (string str : prefix) cout << str << endl;
		cout << endl;
	}

	return 0;
}

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<memory>
using namespace std;
struct Node
{
    int count;
    shared_ptr<Node> next[26];
    Node():count(0){};

};

int main()
{
    int n;
    while(cin>>n)
    {
        vector<string> v(n);
        for(auto &s:v)
            cin>>s;
        shared_ptr<Node> root= make_shared<Node>();

        for(auto &s:v)
        {
            auto cur=root;
            int len =s.size();
            for(int i=0;i<len;i++)
            {
                if(!(cur->next[s[i]-'a']))
                    cur->next[s[i]-'a'].reset(new Node());
                cur->next[s[i]-'a']->count++;
                cur=cur->next[s[i]-'a'];
            }
        }
        for(auto &s:v)
        {
            auto cur=root;
            for(int i=0;i<s.size();i++)
            {
                 cout<<s[i];
                if(cur->next[s[i]-'a']->count==1)
                      break;
                cur =cur->next[s[i]-'a'];
                
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, i, j, k;
    while(cin >> n) {
        pair<string, int> a[1000];
        for (i = 0; i < n; ++i) {
            cin >> a[i].first;
            a[i].second = 0;
        } 
        for (i = 0; i < n - 1; i++)
        for (j = i + 1; j < n; ++j) {
            string s1 = a[i].first;
            string s2 = a[j].first;
            int len1 = s1.size(), len2 = s2.size();
            for (k = 0; k < len1 && k < len2; ++k) {
                if (s1[k] != s2[k]) {
                    break;
                }
            }
            a[i].second = max(a[i].second, k + 1);
            a[j].second = max(a[j].second, k + 1);
        }
        for (i = 0; i < n; ++i)
            cout << a[i].first.substr(0, a[i].second) << "\n";
        cout << "\n";
    }
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

int main() {
	using namespace std;
	int n;
	while (cin >> n) {
		vector<string> arr(n);
		vector<string> ans(n, "");
		int maxLength = 0;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
			if (arr[i].size() > maxLength) {
				maxLength = arr[i].size();
			}
		}
		for (int i = 0; i < maxLength; i++) {
			map<string, int> map_;
			for (int j = 0; j < n; j++) {
				if (ans[j].size() == 0) {
					string temp = "";
					for (int k = 0; k <= i; k++) {
						temp += arr[j][k];
					}
					if (!map_.count(temp)) {
						map_[temp] = 1;
					}
					else {
						map_[temp] ++;
					}
				}
			}
			for (int j = 0; j < n; j++) {
				if (ans[j].size() == 0) {
					string temp = "";
					for (int k = 0; k <= i; k++) {
						temp += arr[j][k];
					}
					if (map_[temp] == 1 || temp == arr[j]) {
						ans[j] = temp;
					}
				}
			}
		}
		for (int i = 0; i < n; i++) {
			cout << ans[i] << endl;
		}
        cout << endl;
	}
	return 0;
}