poj1934 Trip

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;
}

补充：软件开发 , C++ ,