POJ 1934 Trip LCA 및 반복되지 않는 모든 문자열

Trip
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 1629
 
Accepted: 372
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
acbacba

Sample Output

ababa
abaca
abcba
acaba
acaca
acbaa
acbca

Source
CEOI 2003
 
/* 이전에는 LCA(최대 공통 하위 시퀀스)의 크기만 구했지만 모든 LCA 문자열을 요구하고 중복을 허용하지 않으면 곤란합니다.n을 오랫동안 생각하고 n의 방법을 시도했는데 모두 WA였다.마지막으로 인터넷에 가서 선배들의 문제풀이 보고서를 볼 수밖에 없었는데, 이 문제풀이 보고서를 줄곧 찾지 못했으니, 어쩐지 이 문제AC가 이렇게 적더라니.n구를 뒤져 결국 이박씨오 2003의 문제풀이 보고서를 찾았는데, 보고 나서야 문득 크게 깨달았다.하지만 이것도 쉽게 생각해 낼 수 있는 것은 아니다.(1) 우선 두 개의 입력열의 loc[i][j]를 각각 계산한다.str1의loc[i][j]는str1에서 위치 i와 그 앞에 위치하고 i에서 가장 가까운 자모 j의 위치를 나타낸다면loc[i][j]=i를str[i]==j로 얻을 수 있다.loc[i - 1][j]str[i]!=j(2) 우선 입력열에 대한 계산이 바뀌어야 한다. 즉, LCA[i][j]는 두 개의 줄str1[1...i]와str2[1...j]의 LCA 길이를 나타낸다. LCA[i][j]=LCA[i-1][j-1],str1[i]=str2[j];max(LCA[i-1][j], LCA[i][j-1]), str1[i]! =str2 [j] (2) 그리고 두 개의 열의 끝에서 밀어냅니다. 현재 처리된 두 개의 열의 위치가 각각 n, m라고 가정하면 (1) 만약str1 [n] =str2 [m], 현재 문자열str1 [n]을 결과 문자열res에 추가하고 n, m의 위치는 각각 앞으로 1을 n-1, m-1(2) 만약str1 [n]! =str2[m], 모든 26개의 알파벳을 훑어보고 LCA[loc1[n][k], loc2[m][k]]]의 가장 큰 k의 위치를 찾아 앞으로 추진하여 n, m를 각각 loc1[n][k], loc2[m][k]로 갱신하고 이 문제를 통해 LCA에 대한 인식을 더욱 깊이 있게 하여 ing*/#include #include #include #define MAX_N 10005 #define MAX_LEN 100 #define maxv(a, b) ((a) >= (b) ? (a) : (b)) using namespace std; struct str { string seq; }strs[MAX_N + 1]; int n, maxLen; string str1, str2; int len1, len2; int lcs[MAX_LEN + 1][MAX_LEN + 1]; int loc1[MAX_LEN + 1][27]; int loc2[MAX_LEN + 1][27];//계산 locvoid getLoc(stringstr, int loc[][27]) {int i, j,len=str.length();memset(loc,0, sizeof(loc));for(i=1;i<=len;i++) {for(j=1;j<=26;j+) {if(str[i-1]'a'+1=j)loc[i]=i;else {if(loc[i-1]=0)=0)continue;loc[i]] [j] = loc[i - 1][j];}}}}}//계산 LCS void getLCS() {int i, j;memset(lcs, 0xbf,sizeof(lcs));for(i=0;i<=maxv(len1,len2);i+)lcs[i][0]=lcs[0][i]=0;for(i=1;i<=len1;i+){for(j=1;j<=len2;j++){if(str1[i-1]=str2[j-1])lcs[i]=lcs[i]=lcs] [j-1] + 1;else {if(lcs[i-1][j]>lcs[i][j-1])lcs[i][j]=lcs[i-1];elseif(lcs[i-1][j] maxV) {maxV = lcs[pp1][pp2];maxP1 = pp1;maxP2 = pp2;}//찾은 최대치에서 for(i=1;i<=26;i++) {intpp1=loc1[p1+1][i],pp2=loc2[p2+1][i];if(pp1-1===p1&pp2-1==p2)continue;if(lcs[pp1]=maxV)solve(pp1-1,pp2-1,res)}}}}}bool compare(const str &s1, const str &s2) { return s1.seq <= s2.seq; } int main() { cin>>str1>>str2; maxLen = INT_MIN; n = 0; len1 = str1.length(); len2 = str2.length(); string res = ""; getLoc(str1, loc1); getLoc(str2, loc2); getLCS(); solve(len1 - 1, len2 - 1, res); sort(strs, strs + n, compare); for(int i = 0; i < n; i++) { cout<