UVa 10391 - Compound Words-白红宇

UVa 10391 - Compound Words

阅读量：4953 次

发布时间：2019-06-12

本文共 1625 字，大约阅读时间需要 5 分钟。

题意

按字典序输入一些单词, 查找单词是否是由两个单词复合而成的并将复合单词输出

例如 ab + normal = abnormal

思路

用 vector< string> 存下string

题给数据范围120,000单词, 全部暴力枚举一遍复杂度肯定高了

考虑到因为输入是按字典序的

那么可以记录下每个字母开头的下标范围

( 这里用到两个标记数组 m[30], n [30] )

WA了几次, 最后发现是因为查找输出顺序有误

最后用map标记了一下 , 统一输出就AC了

AC之后学习网上题解的大多数方法用的是hash函数

还有 .substr() 枚举拆分字符串, 复杂度也在可控范围内

记录

C++ primer上关于string搜索函数 .find()

这里搜索返回值的数据类型是 size_type 即 size_t

//在str当中查找第一个出现的str2，找到则返回出现的位置，否则返回结尾    string str ("I am an acmer!");    string str2 ("acmer");    size_t found = str.find(str2);    if (found!=std::string::npos)        cout << "Find " << str2 << " at : " << found << endl;

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include
        
         #include 
         
          #include 
          using namespace std;vector
           
             vec;map
            
              mrk;int m[30],n[30];int main(){ int num = 0, i = 0, j; string s; std::size_t f; memset(n,0,sizeof(n)); while( cin >> s ){ vec.push_back(s); num++; if( m[s[0]-'a'] == 0 ) m[s[0]-'a'] = num; n[s[0]-'a']++; } for( i = 0; i < num; i++ ){ int len = vec[i].length(); int x = vec[i][0]-'a'; //cout <<"first" << i << ' ' << m[x]+n[x]-1-1 << ' ' << endl; for( j = i; j < m[x]+n[x]-1; j++ ){ f = vec[j].find(vec[i]); if(f != std::string::npos){ int xx = vec[j][len] - 'a'; if( m[xx] == 0 ) continue; //cout << "second" << m[xx]-1 << ' ' << m[xx]+n[xx]-1-1 << endl; for( int k = m[xx]-1; k < m[xx]+n[xx]-1; k++ ) if( vec[i] + vec[k] == vec[j] && !mrk.count(j)){ pair
             
               p(j,1); mrk.insert(p); break; } } } } for( i = 0; i < num; i++ ) if( mrk.count(i) ) cout << vec[i] << endl; return 0;}