Codeforces-963 D Frequency of String-白红宇

Codeforces-963 D Frequency of String

阅读量：7055 次

发布时间：2019-06-28

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

题意：给你一个字符串，进行q次询问操作，每次给你一个n和一个子串，问能否在字符串中出现n次子串，若可以输出最短长度的n次子串，否则输出-1

题解：优雅的暴力哈希，枚举每一个不同种长度的子串，注意是不同种！因为这样子能减少枚举的次数，这是一个巨大的优化，同时用unordered_map这个不按key排序的map，减少logn的STL复杂度。（我就说一定存在不按照key排序的map啊啊啊）

还是我很挫的代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include
                
                 //CLOCKS_PER_SEC#define se second#define fi first#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define Pii pair
                 
                  #define Pli pair
                  
                   #define ull unsigned long long#define pb push_back#define fio ios::sync_with_stdio(false);cin.tie(0)const int N=1e5+5;const ull base=131;const int INF=0x3f3f3f3f;using namespace std;ull Hash[N];ull p[N];unordered_map
                   
                    mp;ull get(int l,int r){ if(l==0)return Hash[r]; return Hash[r]-Hash[l-1]*p[r-l+1];}int L[N],id[N],a[N];ull H[N];bool cmp(int x,int y){ return L[x]
                    
                     
                      ans[N];int main(){ fio; string str; cin>>str; int len=str.length(); Hash[0]=str[0]; p[0]=1; for(int i=1;i
                      
                       >n; for(int i=1;i<=n;i++){ string op; cin>>a[i]; cin>>op; id[i]=i,L[i]=op.length(); ull u=0; for(int j=0;j

转载于:https://www.cnblogs.com/Mrleon/p/8886982.html

你可能感兴趣的文章

IBM中国开发中心吉燕勇：通过Cloud Data Services打造新型认知计算数据分析云平台...