fzu 2137 字符串hash或者后缀数组 - c++编程基础

奇异字符串

Time Limit:1000MS

Memory Limit:32768KB

64bit IO Format:%I64d & %I64u

[Submit] [Go Back] [Status]

Description

seen喜欢一种特殊的字符串，seen称这种字符串为奇异字符串。奇异字符串可以表示为AxA这种形式，A为一个任意非空字符串，只包含小写字母，x为一个不在A中出现过的小写字母。seen认为一个长度为d的奇异字符串的价值为d*d，不是奇异字符串的字符串没有价值。现给一个只包含小写字母的字符串，统计其所有子串的价值总和。一个字符串的子串是指其中连续的一段字符构成的字符串。这里相同的子串如果在原串中出现的位置不同则视为不同，需要分别进行统计。

Input

第一行一个整数T，表示有T组数据。

每组数据输入一行只包含小写字母的非空字符串，长度不超过100000。

Output

对于每组数据输出一行表示所有子串的价值总和。

Sample Input

1
abcdabc

Sample Output

[Submit] [Go Back] [Status]

好久前的一题，可以后缀数组，也可以字符串hash，若菜有点弱，目前只会hash，后缀数组暂时没实现出来，就贴一个字符串hash的代码，后缀数组实现出来再贴上去

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-9 22:25:06
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef unsigned long long ll; const ll maxn=100100; ll hash[maxn],base[maxn]; char s[maxn]; void init(ll len){ ll seed=131; hash[0]=0;base[0]=1ll; for(ll i=1;i<=len;i++){ hash[i]=hash[i-1]*seed+s[i]; base[i]=base[i-1]*seed; } } ll gethash(ll L,ll R){ return hash[R]-hash[L-1]*base[R-L+1]; } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int T; cin>>T; while(T--){ scanf("%s",s+1); ll len=strlen(s+1); init(len); ll ans=0; for(ll i=2;i
                
                 =1&&R<=len){ if(s[L]==s[i]||s[R]==s[i])break; if(gethash(L,i-1)==gethash(i+1,R)) ans+=(ll)(2*(i-L)+1)*(2*(i-L)+1); L--;R++; } } printf("%I64u\n",ans); } return 0; }