M - Palindromic String

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 128000/128000KB (Java/Others)

Submit Status

秋实大哥喜欢探索新鲜事物，最近他发明了一种新型回文串，叫K重回文串！今天他想用它来考考小朋友们。

秋实大哥给出了与K重回文串有关的信息

任何字符串都属于0重回文串，包括空字符串。

一个长度为N的字符串S，S是K(k≥1)重回文串，当且仅当S是回文串，且其长度为⌊N2⌋的前缀和长度为⌊N2⌋的后缀是K−1重回文串。

如果一个字符串是K重回文串，则称该字符串有一个回文值为K。一个字符串可以有多个回文值，比如S=abaaba，其回文值可为0，1，2，3。

字符串的最大回文值是该字符串所有回文值的最大值。

若字符串S的最大回文值≥1，则S一定是回文串。

一个字符串S，如果其正着读和反着读是一样的，则称S是回文串，比如aabaa，aba，a。但abc，abab，aacba就不是回文串。

一个长度为N的字符串S，其有N+1个前缀和N+1个后缀（不一定非空），比如abcde，有6个前缀，分别是空字符串，a，ab，abc，abcd，abcde；有6个后缀，分别是空字符串，e，de，cde，bcde，abcde。

秋实大哥给你一个字符串S，他想问问你，S所有前缀的最大回文值之和是多少？

Input

第一行输入一个字符串S（0<|S|≤2⋅106），S包含大写英文字母（A－Z），小写英文字母（a－z），数字（0－9）

Output

输出一个整数，表示S所有前缀的最大回文值之和。

Sample input and output

Sample Input	Sample Output
z	1
a2Az	1
abacaba	6
CCeCeCCCee	4
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ	231

Hint

下面对样例3进行解释：

abacaba有8个前缀，分别是空字符串，a，ab，aba，abac，abaca，abacab，abacaba；

设P(i) 表示第 i 个前缀的最大回文值，且空字符串是第0个前缀；

则P(0)=0，P(1)=1，P(2)=0，P(3)=2，P(4)=0，P(5)=0，P(6)=0，P(7)=3；那么∑7i=0P(i)=6。

解题报告：

这是一道阅读题，读懂了就很简单，我们的目的就是快速判断某一前缀是否是回文串，使用hash进行判断即可

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int maxn = 2e6 +  , p1 =  , p2 =  , mod1 = 1e9 + ,mod2 = 1e9 + ;

char s[maxn];

int  len,ans[maxn];

ll hash1[maxn],hash3[maxn],px[maxn];

void init_hash()

{

   hash1[] =  ,hash3[] = ;

   for(int i =  ; i <= len ; ++ i)

     hash1[i] = (hash1[i-]*p1 + s[i]) % mod1;

   for(int i = len ; i >= ; -- i)

     hash3[len-i+] = (hash3[len-i]*p1 + s[i]) % mod1;

}

int gethashvalue(int l,int r,int id)

{

   ll ans;

   if (id == )

    {

        ans = (hash1[r] - hash1[l-]*px[r-l+])%mod1;

        if (ans < )

         ans += mod1;

        return ans;

    }

   else if(id == )

    {

        ans = (hash3[r] - hash3[l-]*px[r-l+])%mod1;

        if (ans < )

         ans += mod1;

        return ans;

    }

}

int main(int argc,char *argv[])

{

  scanf("%s",s+);len = strlen(s+);init_hash();ans[] = ;

  px[] = ;

  for(int i =  ; i <= len ; ++ i)

    px[i] = (px[i-]*p1)%mod1;

  for(int i =  ; i <= len ; ++ i)

   {

         if ( gethashvalue(,i,) == gethashvalue(len-i+,len,))

              ans[i] = ans[i/]+;

         else

          ans[i] = ;

   }

  long long out = ;

  for(int i =  ; i <= len ; ++ i)

   out += ans[i];

  printf("%lld\n",out);

  return ;

}

巴特西

UESTC_Palindromic String 2015 UESTC Training for Search Algorithm & String<Problem M>

M - Palindromic String

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 128000/128000KB (Java/Others)

任何字符串都属于0重回文串，包括空字符串。

一个长度为N的字符串S，S是K(k≥1)重回文串，当且仅当S是回文串，且其长度为⌊N2⌋的前缀和长度为⌊N2⌋的后缀是K−1重回文串。

如果一个字符串是K重回文串，则称该字符串有一个回文值为K。一个字符串可以有多个回文值，比如S=abaaba，其回文值可为0，1，2，3。

字符串的最大回文值是该字符串所有回文值的最大值。

若字符串S的最大回文值≥1，则S一定是回文串。

一个字符串S，如果其正着读和反着读是一样的，则称S是回文串，比如aabaa，aba，a。但abc，abab，aacba就不是回文串。

一个长度为N的字符串S，其有N+1个前缀和N+1个后缀（不一定非空），比如abcde，有6个前缀，分别是空字符串，a，ab，abc，abcd，abcde；有6个后缀，分别是空字符串，e，de，cde，bcde，abcde。

秋实大哥给你一个字符串S，他想问问你，S所有前缀的最大回文值之和是多少？

Input

Output

Sample input and output

Hint

下面对样例3进行解释：

abacaba有8个前缀，分别是空字符串，a，ab，aba，abac，abaca，abacab，abacaba；

设P(i) 表示第 i 个前缀的最大回文值，且空字符串是第0个前缀；

则P(0)=0，P(1)=1，P(2)=0，P(3)=2，P(4)=0，P(5)=0，P(6)=0，P(7)=3；那么∑7i=0P(i)=6。

最新文章

热门文章

巴特西

UESTC_Palindromic String 2015 UESTC Training for Search Algorithm & String<Problem M>

M - Palindromic String

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 128000/128000KB (Java/Others)

任何字符串都属于0重回文串，包括空字符串。

一个长度为N的字符串S，S是K(k≥1)重回文串，当且仅当S是回文串，且其长度为⌊N2⌋的前缀和长度为⌊N2⌋的后缀是K−1重回文串。

如果一个字符串是K重回文串，则称该字符串有一个回文值为K。一个字符串可以有多个回文值，比如S=abaaba，其回文值可为0，1，2，3。

字符串的最大回文值是该字符串所有回文值的最大值。

若字符串S的最大回文值≥1，则S一定是回文串。

一个字符串S，如果其正着读和反着读是一样的，则称S是回文串，比如aabaa，aba，a。但abc，abab，aacba就不是回文串。

一个长度为N的字符串S，其有N+1个前缀和N+1个后缀（不一定非空），比如abcde，有6个前缀，分别是空字符串，a，ab，abc，abcd，abcde；有6个后缀，分别是空字符串，e，de，cde，bcde，abcde。

秋实大哥给你一个字符串S，他想问问你，S所有前缀的最大回文值之和是多少？

Input

Output

Sample input and output

Hint

下面对样例3进行解释：

abacaba有8个前缀，分别是 空字符串，a，ab，aba，abac，abaca，abacab，abacaba；

设P(i) 表示第 i 个前缀的最大回文值，且空字符串是第0个前缀；

则P(0)=0，P(1)=1，P(2)=0，P(3)=2，P(4)=0，P(5)=0，P(6)=0，P(7)=3；那么∑7i=0P(i)=6。

最新文章

热门文章

abacaba有8个前缀，分别是空字符串，a，ab，aba，abac，abaca，abacab，abacaba；