UVa 1405 - The Ultimate Password

제목:
블로거는 이 난을 쓰는 것을 좋아하지 않지만, 이 문제의 뜻을 감안하면 좀 복잡하다.
n개의 문자열이 있습니다. 문자열을 회전할 수 있는 상황에서 문자열을 연결하여 문자열의 길이를 가장 짧게 하는 방법을 찾습니다. 예를 들어 aabb와 bbcc는 aabbcc로 연결하고 가장 짧은 전제에서 가장 작은 사전 문자열을 출력할 수 있습니다.
팁:
1. 하나의 dp문제로 사고방식이 복잡하지 않다.
2. 제목 중 하나: the state of any lock is not shorter than the state of its previous lock, 문자열의 길이가 단조롭게 증가하는 것을 가리키지만 증가하는 것은 사실 처리하기 어렵다. 왜냐하면 다음 문자열은 앞의 몇 개의 문자열과 결합할 수 있기 때문에 이 상태는 표시할 수 없기 때문이다.
상기 두 가지 힌트를 자세히 생각해 보세요. 만약 당신의 영광이 번쩍인다면 어서 손을 대세요.
3. 속2, 그래서 너는 전체 서열을 거꾸로 할 수 있고, 사전 서열도 분명히 거꾸로 처리해야 한다(하지만 이것은 결코 어렵지 않다)
4. dp[i][j]는 i번째를 처리하고 i번째 문자열은 이 문자열의 j번째 문자로 머리를 돌리는 회전 방식(약간 돌고 스스로 뇌보)을 사용하고 전이 방정식은 어렵지 않다.
참고:
1. 시간 초과 문제: 본 문제는 접두사 접두사 판단이 같은 방법을 추가합니다. 접두사 수조에 익숙하지 않기 때문에 (여기서 사용할 수 있을지 없을지도 몰라요) 블로거는hash를 사용합니다. 자세한 것은same() 함수를 보십시오.

//
//  main.cpp
//  UVa1405
//
//  Created by Fuxey on 15/10/20.
//  Copyright © 2015  corn.crimsonresearch. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;
typedef unsigned long long ull;
const int INF = 1<<29;
const ull hash_num = 10331007;

// d[i][j] upto i and end with the jth rotation of ith string
int d[250][150];
string s[250];
string rot[250][150];
ull hashes[250][150][150];
ull acu[200];
inline int same(int x1 , int y1 , int x2 , int y2)
{
    for(int i=(int)min(s[x1].size(), s[x2].size());i>=0;i--)
        if(hashes[x1][y1][s[x1].size()] == hashes[x2][y2][i]+hashes[x1][y1][s[x1].size()-i]*acu[i])
            return i;
    return -1;
}

bool smaller(string& s1 , string& s2)
{
    for(int i=1;i<=min(s1.size(), s2.size());i++) if(s1[s1.size()-i]!=s2[s2.size()-i])
        return s1[s1.size()-i]<s2[s2.size()-i];
    return false;
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    acu[0] = 1;
    for(int i=1;i<=120;i++) acu[i] = acu[i-1]*hash_num;
    
    int t;
    cin>>t;
    while(t--)
    {
        string op;
        cin>>op;
        reverse(op.begin(), op.end());
        
        int last = 0 , n = 0;
        for(int i=0;i<op.size();i++)
        {
            for(;i<op.size() && op[i]!=';';i++) ;
            s[++n] = op.substr(last , i-last);
            last = i+1;
        }
        
        for(int i=1;i<=n;i++) rot[i][0] = s[i];
        for(int i=1;i<=n;i++) for(int j=1;j<s[i].size();j++) rot[i][j] = rot[i][j-1].substr(1,s[i].size()-1)+rot[i][j-1][0];
        for(int i=1;i<=n;i++) for(int j=0;j<s[i].size();j++) for(int k=1;k<=s[i].size();k++)
            hashes[i][j][k] = hashes[i][j][k-1]*hash_num+(ull)(rot[i][j][k-1]-'A'+10);
        
        for(int i=1;i<=n;i++) for(int j=0;j<s[i].size();j++) d[i][j] = INF;
        for(int i=0;i<s[1].size();i++) d[1][i] = (int)s[1].size();
        
        for(int i=2;i<=n;i++) for(int j=0;j<s[i].size();j++) for(int k=0;k<s[i-1].size();k++)
            d[i][j] = min(d[i][j] , d[i-1][k]+(int)s[i].size()-same(i-1,k, i,j));
        
        int sup = INF;
        for(int i=0;i<s[n].size();i++) sup = min(sup , d[n][i]);
        
        string Min = "[";
        int x = 0;
        for(int i=0;i<s[n].size();i++) if(d[n][i]==sup && smaller(rot[n][i] , Min)) Min = rot[n][i] , x = i;
        
        string res = rot[n][x];
        for(int i=n-1;i>=1;i--)
        {
            Min = "[";
            int nextx = 0;
            for(int j=0;j<s[i].size();j++)
                if(d[i+1][x] == d[i][j]-same(i,j, i+1,x)+s[i+1].size() && smaller(rot[i][j] , Min))
                    Min = rot[i][j] , nextx = j;
            int h = same(i, nextx, i+1,x);
            res = rot[i][nextx].substr(0 , s[i].size()-h)+res;
            x = nextx;
        }
        
        reverse(res.begin(), res.end());
        cout<<res<<endl;
    }
    
    return 0;
}