Trip
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2773 Accepted: 703
Description
Alice and Bob want to go on holiday. Each of them has planned a route, which is a list of cities to be visited in a given order. A route may contain a city more than once.
As they want to travel together, they have to agree on a common route. None wants to change the order of the cities on his or her route or add other cities. Therefore they have no choice but to remove some cities from the route. Of course the common route should be as long as possible.
There are exactly 26 cities in the region. Therefore they are encoded on the lists as lower case letters from 'a' to 'z'.
Input
The input consists of two lines; the first line is Alice's list, the second line is Bob's list.
Each list consists of 1 to 80 lower case letters with no spaces inbetween.
Output
The output should contain all routes that meet the conditions described above, but no route should be listed more than once. Each route should be printed on a separate line. There is at least one such non-empty route, but never more than 1000 different ones. Output them in ascending order.
Sample Input
abcabcaa
acbacbaSample Output
ababa
abaca
abcba
acaba
acaca
acbaa
acbcaSource
CEOI 2003
這道題可以分解為三個問題，
1、求最長公共子字符串 常規方法 lcs()
2、存下每個字母在前 i 個字符中最後一次出現的位置，（i<=len）
vis1[i][j] = { 到下標i為止，字符j在字串a中最後一次出現的下標 }
vis2[i][j] = { 到下標i為止，字符j在字串b中最後一次出現的下標 }
3、枚舉最長公共串的每一位，從最後一位往前枚舉
首先找dp[i][j]=len，就是說i，j在兩個字符串中所對應的字符相同，且可以作為最長公共串的最後一位
再接著枚舉len-1，這樣就可以不重復找出所有的組合
用set存，按字母排序輸出
後面兩個方法才是關鍵，根本想不到啊。。好神奇
感想：
開始直接找到一個輸出一個，因為我覺得按字母順序找的，直接輸出應該是排好序的啊，結果不是。。
但我還是覺得應該是按字母序的，因為每一個len，都是從a到z找一遍，這樣的話，都是小字母優先啊，求解釋。。。
反正輸出來就不對了。。
於是照各位大神的用了一個set容器，存入set的成員是按從小到大排的，且沒有重復成員的（可以用來判重）
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<set>
using namespace std;
int dp[105][105],l1,l2,l,vis1[105][105],vis2[105][105];
char s1[105],s2[105],save[105];
set<string> ans;
void lcs()
{
int i,j;
memset(dp,0,sizeof dp);
l1=strlen(&s1[1]);
l2=strlen(&s2[1]);
for(i=1;i<=l1;i++)
{
for(j=1;j<=l2;j++)
{
if(s1[i]==s2[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
}
}
l=dp[l1][l2];
}
void find(int a,int b,int len)
{
int i,p1,p2;
if(len<=0)
{
ans.insert(&save[1]);
// puts(&save[1]);
return ;
}
if(a>0&&b>0)
{
for(i=0;i<26;i++)
{
p1=vis1[a][i];
p2=vis2[b][i];
if(dp[p1][p2]==len)
{
save[len]='a'+i;
find(p1-1,p2-1,len-1);
}
}
}
}
int main()
{
int i,j;
while(gets(&s1[1])!=NULL)
{
gets(&s2[1]);
lcs();
memset(vis1,0,sizeof vis1);
memset(vis2,0,sizeof vis2);
for(i=1;i<=l1;i++)
for(j=0;j<26;j++)
{
if(s1[i]==j+'a')
vis1[i][j]=i;
else vis1[i][j]=vis1[i-1][j];
}
for(i=1;i<=l2;i++)
for(j=0;j<26;j++)
{
if(s2[i]==j+'a')
vis2[i][j]=i;
else vis2[i][j]=vis2[i-1][j];
}
memset(save,0,sizeof save);
save[l+1]='\0';
find(l1,l2,l);
set<string>::iterator it;//定義一個迭代器 就當指針來理解吧。。
for(it=ans.begin();it!=ans.end();it++)
printf("%s\n",(*it).c_str());
}
return 0;
}
