SRM 604 DIV2 250-白红宇

SRM 604 DIV2 250

阅读量：4514 次

发布时间：2019-06-08

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

题意：给你一个字符串向量，问你有中间多少个串循环相等（循环相等的意思就是 “ab”，“ba”，经过移位以后还相等的字符串）

解题思路：KMP，这种字符串有一个性质，就是如果 a的长度等于b的长度，且能在 a+a 中匹配到b，则可以断定这两个字符串循环相等

解题代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         
                          #include 
                          
                           #include 
                           
                            #include 
                            
                             using namespace std;#define PB push_back#define MP make_pair#define REP(i,n) for(i=0;i<(n);++i)#define FOR(i,l,h) for(i=(l);i<=(h);++i)#define FORD(i,h,l) for(i=(h);i>=(l);--i)typedef vector
                             
                               VI;typedef vector
                              
                                VS;typedef vector
                               
                                 VD;typedef long long LL;typedef pair
                                
                                  PII;int kmp(string a, string b){ int pi[100]; int m = b.size(); memset(pi,0,sizeof(pi)); pi[0] = -1; int k = -1 ; for(int i = 1 ;i < m ; i ++) { while(k >= 0 && b[k+1] != b[i]) k = pi[k]; if(b[k+1] == b[i]) k = k +1; pi[i] = k; } int n = a.size(); int q = -1 ; for(int i = 0;i < n;i ++) { while(q >= 0 && b[q+1] != a[i]) q = pi[q]; if(b[q+1] == a[i]) q = q +1; if(q == m -1) { return 1; } } return 0 ; }class FoxAndWord{ public: int howManyPairs(vector 
                                 
                                   words) { int k = words.size(); int sum = 0 ; for(int i = 0;i < k ;i ++) for(int j = i + 1;j < k; j ++) { string temp = words[i] + words[i]; if(kmp(temp,words[j])&& words[i].size() == words[j].size()) { sum ++ ; } } return sum ; }};

代码

转载于:https://www.cnblogs.com/zyue/p/3515907.html

你可能感兴趣的文章