Isomorphic Inversion

Isomorphic Inversion

Let $s$ be a given string of up to $10^6$ digits. Find the maximal $k$ for which it is possible to partition $s$ into $k$ consecutive contiguous substrings, such that the $k$ parts form a palindrome. More precisely, we say that strings $s_0,s_1,…,s_{k−1}$ form a palindrome if $s_i=s_{k−1−i}$ for all $0\le i< k$.

In the first sample case, we can split the string 652526 into $4$ parts as 6|52|52|6, and these parts together form a palindrome. It turns out that it is impossible to split this input into more than $4$ parts while still making sure the parts form a palindrome.

Input

• A nonempty string of up to $10^6$ digits.

Output

• Print the maximal value of $k$ on a single line.

Sample Input 1	Sample Output 1
652526	4

Sample Input 2	Sample Output 2
12121131221	7

Sample Input 3	Sample Output 3
123456789	1

Sample Input 4	Sample Output 4
132594414896459441321	9

题意

给出一个由数字组成的字符串，让你对这个字符串进行切割，使其变成一个回文串，例如 $652526$ 且切割为 $6|52|52|6$ 之后，把 $52$ 看作一个字符，那么这个串就是回文的了，如果还不理解，看第二个样例，切割为 $1|2|12|113|12|2|1$，各部分分别看作一个字母，即变成回文串了，现在让你求最多的切割次数。

解决方案

显然，这个题目可以贪心解决，即用两个指针，一个从前面，一个从后面，同时开始扫，然后判断扫到的这两部分字符串是否相同，相同则切割，否则接着往下扫，直到两者是同一个串（即最中间的对称轴）或者 $i = j$ 。

这样做的时间复杂度是 $O(n^2)$，显然过不了。我们可以看出，这里能够进行优化的只有字符串比较那一部分了，但是直接比较 $O(n)$ 肯定不行，有什么 $O(1)$ 比较的方法吗？这里就要用到字符串哈希的技术了。

字符串哈希比较简单，这里不细讲，推荐一篇博客：

字符串哈希

讲的非常详细。

代码

#include <bits/stdc++.h>
#define zpw                    \
  ios::sync_with_stdio(false); \
  cin.tie(NULL);               \
  cout.tie(NULL)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn = 1e6 + 10;
const ull p = 1610612741;

ull Hash[maxn];
ull po[maxn];
char s[maxn];
int len;

void init() {
  for (int i = 1; i <= len; i++) {
    Hash[i] = Hash[i - 1] * p + s[i] - '0' + 1;
  }
  po[0] = 1;
  for (int i = 1; i <= len; i++) {
    po[i] = po[i - 1] * p;
  }
}

ull getHash(int l, int r) { return Hash[r] - Hash[l - 1] * po[r - l + 1]; }

int main() {
  zpw;
  cin >> s + 1;
  len = strlen(s + 1);
  init();
  int ans = 0;
  int i = 1, j = len;
  while (i < j) {
    int t = 1;
    while (2 * t <= j - i + 1 &&
           getHash(i, i + t - 1) != getHash(j - t + 1, j)) {
      t++;
    }
    if (2 * t > j - i + 1) {
      ans++;
      break;
    } else {
      ans += 2;
      i += t;
      j -= t;
    }
  }
  if (i == j) {
    ans++;
  }
  cout << ans << endl;
  return 0;
}

感想

                                               .......@^../..........,/[...........[@]..........=^.
                                               ......=@\.=^.......,[...................\@].......@`
                                               ......=@OOOOO\`..,.......]@@/[[\@@\]......\O\.....=^
                                                ..../@@@@@O@@@@@\...,/[............\@\`...,OO....,@
                           ........... ..........,@@@@@OOOOO@@@@@@@/....   ..   ....@OO@`..,[.....@
                            ....... ......  .. .,@@@@@@@@@@@@@@@@@@@^...       .....@OOO@\.......=@
                        ..............]]]]]]]]]]/@@@@@@@@@@@@@@@@@@@@....   ..  ...,@@OO@O\......=^
                        ......]//[...................[[\@@@@@@@@@@/[@\..       ...,@O@OO@O@......@.
                .........,//`................................[@@@O`./O@`........,/@O@OO@OO@^....@`.
                  ...,//`..........,`...........................,@@OO@@......,/@@O@OOOOOOO@`..,/...
            ......./[.............OO`.........]..........,\`.......,@@\]]/@@@OO@@OOOOOOOOO/]@/...  
            ....,@`..............=O^.........=O.............,\........\@OOOOOOOOOOOOOOOO@@/`.....  
         . ...,/.................O/........../`...............=]........\@@@@\@@@@@@/[[.......... .
        . ..,@`................./O^..........@O................,@^........\\.[\@\`............  .. 
       ..../^..................=O@^.........=@O^.....=`.........,@O........\@\`..,[@@@]].......,\..
        .,/.......=......./O..,@O@..........=@@O`....,O...........@O`......=@@@O`.......,[\@@/`....
........=^.......=`...../\o/..O/o@..........@OO@O....=\O...........\O`.....=@^\@OO\..@[[........  .
......./^......./O.,/@@@@@@@]=@`=@..........@/\O@O...=\@O...........=@...../^..\@OOOO`,@`........  
. ..../O`......,@/`.=@//.=O^.@`.=@^.........@^\O@@/[[\@@@\...........,\.........@OO.[OO\`[@`.......
.....=OO,`...../O..@Oo`..o=^/^..,\^.........@^.\\/@^..@=o\@@\.........,@`....,^.=@OOO]......[@\... 
....=@OO^.....=@O,@o/....=O@/....O\.........@^..=o\\\.\.=o/@.\..........@`../@...@@OOOOO]......,\@@
.. .@@OO.....,@O@@o......=/@,..../@.......=.@^..,[[ooO/^..oo@`...........\@O@....@@OOO@@@@@@\]],]@/
...=@OO^.....@@@O^......=^o*.....=O/`..*../O\^.....,oo.=...\o@\...........,\....=@@@@@@@@@@@[[`....
...@@O@.....@\@\........O@@......,/@O.***.@/@@.....=`,*.....,o/@`...........@...@@O@OOO@`......... 
..=@O@^....=/O^.......,^..@@......=OO\****@o,@.....=@@\......=oO@\.....,.....\`.OOO@^[@O@@`........
..=@//^...,@oO........@\.]@@^....../O/\,*=@o^,`...@..@@@......o/OO@\...,^.....,@/O@@^...,\@@@]`.. .
..@@.@....@O,/.......=@@@@@@^.......o,o\*,@o^....=^..@@@^.....o/@OOO@\`.=`......,@@O\............  
.=@^=/...=@^.........=@@@@@@..........=oO*@,o....@@@@@@@^.....=O@^.OOO@\.=`.......,\/............  
.@@.=^...@@..........=@@@@@/...........,oO@`....=@@@@@@@^.....,O@^..,OOO@@/@\`......,@`.........   
.@^.@^..=@@...........@@@@/.............,oO^.....@@@@@@/.......o@^....,\@OOO@OO@O[[[[[..........   
=@..@^..=@@...............................\^.....@@@@@@........o@^......@O[\`/^.*[.=............   
,@..@^../O@^......................................[@/`.........=@.......@/./@O^....=............   
.@..@^..@O@^...................................................=@.......@@@OOOO..../............   
....@^..OOO@`..................................................=@.......@,@OOOO^...@............   
  ..@^..OOOO@..................................................=@......=/.,@OOO^...@............   
....=^..O^OO@\..............@@]]]`.............................=@......=^...@OO^...@............   
  . =@..=.=OOO@`............=@@@@@@@@@@@@@@@@..................=@......=^....@OO...@............   
. ...@^...*OOOO@@............@OO@@@@@@@@@@@@/................../@......@.....,@O...@............   
. ...=\....\OO@OO@@`..........\@OOOO@@OOOO/`...................@O.....,@......=@^..@^...........   
......@`...*OO@OO@OO@\...........,[@@@@[`.....................,@O..../=^......=@^..@^...........   
    ..=\....=O@OO@OOOOO@@]`.................................=@@@\...=\/......=@O\..=^...........   
    ...@^....\@O@OOOOOOOOOO/................................../@^..=\@.....,@OOOO..=@....          
    ....@,^...@@OOOOOOOOO@^..................................,@O^.=@@...../@OOO@O^..@...........   
    ....,@=^...@OOOOOOOO@^...................................=@O./@@..../@OOOOOO@O..\^...          
        .,\@^..\@OOO@OOO/....,]]`.................,]]`.......@O\@@/..,@@OOOOOOOO@O`..@..           
        ...\@\..@OO@OOO@.....@*]]]`[\\].]/@].,/@[****,\.....=@@/@^,@@@OO@OOOOOOO@O\..,^.           
        ....@O@`=@@OOO@^.....@OOOOOOOOO@\]/O@@OOOOOO\*@....=@@\@/.=@OOOO@OOOOOOO@@O...=^...........
       ....@=OOO@/@OOO@`....*\@OOOO@@@@@@@@@@@@@OOOO^/`...,@\oo/...@OOOO@OOOOOOO@@O^,..\`....,`[=``
        ../^.OOOOO@OOO@......\@OOO@@@@@//\\O@@@@OOOO^@...=\ooo/....@@OOOO@OOOOOO@@OO.\..@....,*.*..
        .=/..,OO@OOOO@^....../@@@@@@@O@[[[[\@O@@@@@O=^...=o``......@@OO@O@OOOOOO@@OO`.^..@.........

我好蔡啊/(ㄒoㄒ)/~~