uva 10132 - File Fragmentation

点击打开链接uva 10132

题目意思：   有一个人有n个文件，每个文件都是相同的，现在这n个文件的每一个文件都被分成了两部分用字符序列表示，要我们找到原来文件的字符序列。

解题思路：    1：每一个文件都是分裂成两部分，每一种文件都是相同的，那么只要找到最小的长度和最大的长度，那么加起来就是文件的长度记为L。
                     2：知道了文件的长度，那么如果我们从第一个子串假设为S1开始，让它分别和后面的字串相匹配，匹配处理有两种可能AB和BA，如果长度为L，那么我们就把这两种情况全部放进map，那么我们可以知道S1基本上都可以和其中的一种匹配成正确的序列，那么只要枚举一遍这个所有子串，那么我们知道在map里面最多的序列就是正确的序列，因为基本上每一次都可以匹配出一个正确的序列
                     3：最后输出map中second最大的first即可
                     4：map使用简单介绍：如果我们要把s插入map，首先我们先判断s是否在map里面，用find函数查找，如果存在直接m[s]++，如果不存在那么我们就令m[s] = 1表示插入
                     5：输入的应用，因为是要读到EOF，所以用gets读入再转化为string，当ch[0] == '\0'时候break

代码：

#include <algorithm> 
#include <iostream> 
#include <cstdlib> 
#include <cstring> 
#include <cstdio>  
#include <cctype>  
#include <cctype>  
#include <cmath>  
#include <stack>  
#include <list>  
#include <map>
using namespace std;  
#define MAXN 10010

int n , len;
string str[MAXN];
map<string , int>m;

void solve(){
    int i , j , l , max;
    int min_len , max_len;
    string s , tmp_str[MAXN] , ans;
    min_len = MAXN ; max_len = 0;
    //找最小长度和最大长度
    for(i = 0 ; i < len ; i++){
        if(str[i].size() < min_len)
            min_len = str[i].size();
        if(str[i].size() > max_len)
            max_len = str[i].size();
    }
    l = min_len+max_len;//文件长度
    m.clear();
    
    map<string , int>::iterator it;//迭代器
    for(i = 0 ; i < len ; i++){
       for(j = i+1 ; j < len ; j++){    
           s = str[i]+str[j];  
           if(s.size() > l)//注意一下这个地方，如果不加会RE，我也搞不懂
               continue;
           if(s.size() == l){
               it = m.find(s);
               if(it != m.end()) m[s]++;
               else  m[s] = 1;
           }
           s = str[j]+str[i];
           if(s.size() == l){
               it = m.find(s);
               if(it != m.end()) m[s]++;
               else  m[s] = 1;
           }
       }
    }
    //找最大值
    max = 0;
    for(it = m.begin() ; it != m.end() ; it++){
        if(max < it->second){
            max = it->second;
            ans = it->first;      
        }
    }
    cout<<ans<<endl;//输出
}

int main(){
   //freopen("input.txt" , "r" , stdin);
    char ch[500];
    scanf("%d%*c%*c" , &n);
    while(n--){
        len = 0;
        while(gets(ch)){
            if(!ch[0]) break;
            str[len] = "";
            for(int j = 0 ; j < strlen(ch) ; j++)
                str[len] += ch[j];
            len++;
        }
        solve();
        if(n)  printf("\n");
    }
    return 0;  
}