Description
给出N个长度不超过5000的只含数字的字符串，你需要回答M次形如i j的询问，对于每次询问用一行输出一个整数表示第i个字符串和第j个字符的最长公共前缀的长度。
比如两个字符串分别为201212和201112，"2"、"20"和"201"都是它们的公共前缀，但最长的公共前缀是"201"，于是就应当输出3。
Input
输入包含多组测试数据。
每组数据的第一行为一个整数N(1<=N<=1000)，表示一共有N个字符串。接下来一共有N行，每行均有一个长度不超过 5000的只含数字的字符串，这N行分别描述了这N个字符串。接下来一行有一个整数M(1<=M<=1000000)，表示一共要回答M次询 问。再接下来一共M行,每行均有两个正整数i j(1<=i,j<=N)，表示你需要回答第i个字符串和第j个字符串的最长公共前缀的长度是多少。
Output
对于每个询问，用一行输出一个整数表示询问的答案。
Sample Input
2
201212
201112
2
1 1
1 2
Sample Output
6
3
这题可能是我写的第一个字典树的题，当时没做出来，后来听了讲解才会。
大体思路：在插入字符串的时候，记录字符串经过的路径，可以得到一个字典树的结点标号序列，容易证明2个字符串的公共前缀所经过的结点是一样的，所以通过二分结点序列来得到2个字符串的最长公共前缀。
View Code #include <stdio.h> #include <string.h> #define MIN(a,b) ((a)<(b)?(a):(b)) #define N 1010 #define LEN 5010 #define NODE 5000010 int id[N][LEN]; int e,next[NODE][11]; int len[N]; int n,m; int ans[N][N]; void add(int cur,int k) {memset(next[e],0,sizeof(next[e]));next[cur][k]=e++; } void init() {int i,j,k,cur;char s[LEN];e=1;memset(next[0],0,sizeof(next[0]));for(i=1;i<=n;i++){scanf("%s",s+1);cur=0;for(j=1;s[j]>='0' && s[j]<='9';j++){k=s[j]-'0';if(!next[cur][k]) add(cur,k);id[i][j]=cur=next[cur][k];}len[i]=j;} } int f(int i,int j) {int mid,min=0,max=MIN(len[i],len[j]);while(min+1!=max){mid=(min+max)>>1;if(id[i][mid]==id[j][mid]) min=mid;else max=mid;}return min; } int main() {int i,j;while(~scanf("%d",&n)){init();scanf("%d",&m);for(i=1;i<=n;i++){for(j=1;j<=i;j++) ans[i][j]=ans[j][i]=f(i,j);}while(m--){scanf("%d%d",&i,&j);printf("%d\n",ans[i][j]);}}return 0; }
