HDU 4416 Good Article Good sentence（后缀自动机）

HDU 2609 How many （最小最大表示法）

forever97 posted @ 2016年9月20日 21:04 in 字符串-后缀自动机 with tags 最小最大表示法 , 503 阅读

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=2609

【题目大意】

给出一些字符串，循环同构的算同一种，问一共有几种

【题解】

考虑循环同构的问题，我们将所有的字符串最小表示，然后用map统计即可。

【代码】

#include <iostream>
#include <string>
#include <map>
using namespace std;
string s;
int n;
map<string,int>M;
string min_max_express(string s,int len,bool flag){  
    int i=0,j=1,k=0;  
    while(i<len&&j<len&&k<len){  
        int t=s[(j+k)%len]-s[(i+k)%len];  
        if(t==0)k++;  
        else{  
            if(flag){if(t>0)j+=k+1;else i+=k+1;}  
            else{if(t>0)i+=k+1;else j+=k+1;}  
            if(i==j)j++;k=0;  
        }  
    }int p=min(i,j);
    s+=s; s=s.substr(p,len);
    return s;
}  
int main(){
    while(cin>>n){
        M.clear();
        for(int i=0;i<n;i++){
            cin>>s;
            M[min_max_express(s,s.length(),1)]++;
        }cout<<M.size()<<endl;
    }return 0;
}