節約每一個字節
Description
John在做一個項目，項目對存儲容量有著近乎苛刻的要求，為此John需要對一些東西進行壓縮存儲。John的第一個問題就是一大堆的字符串，存儲它們太占地方了，為此他想了一個辦法：如果字符串具有相同的後綴，那麼就把這麼字符串的相同後綴和在一起，這樣就能節約一點空間了。比如說有兩個字符串分別為“Programming”和“Something”,這樣它們有相同的後綴ing,這時候就能省去三個字母了。請寫一個程序，計算John這樣做能夠省去多少個字母？
輸入：
第一行是一個整數K，表示有多少個測試用例，以後每個測試用例占n+1行。每個測試用例的第一行為一個整數n（1<=n<=20），從第二行開始依次為n個字符串,字符串由英文字母組成，大小寫敏感。
輸出：
每行輸出一個測試用例的結果。輸出總共節省了多少個字母。
Sample Input
2
2
Programming
Something
3
John
AJohn
BJehn
Sample Output
3
6
#include<iostream>
using namespace std;
char str[20][1000];
int main()
{
int k;
cin>>k;
while(k--)
{
int n;
cin>>n;
int i,j,k1,k2;
for(i=0;i<n;i++)
{
scanf("%s",str[i]);
}
int sum=0,max=0,num=0;
for(i=0;i<n-1;i++)
{
max=0;
for(j=i+1;j<n;j++)
{
num=0;
k1=strlen(str[i])-1;
k2=strlen(str[j])-1;
while(k1>=0&&k2>=0)
{
if(str[i][k1--]==str[j][k2--]) { num++;}
else break;
}
if(max<num)
max=num;
}
sum+=max;
}
cout<<sum<<endl;
}
return 0;
}
摘自 我和我追逐的夢~~~
