Longest string of subroutines

The longest loop substring is the longest loop substring.

Given a string S, find the length of the longest subroutine of S

Example:

The longest substring of the string “PATZJUJZTACCBCC” is “ATZJUJZTA” of length 9

It is necessary to judge whether the substring in [I, j] is palindrome or not. In terms of complexity, the enumeration endpoint needs O(n2) and palindrome judgment needs O(n), and the total complexity is O(n3).

So let’s introduce a solution of O(n2) in dynamic programming.

Let dp[I][j] be S[I] to S[j], if 1, otherwise 0. Thus, according to whether S[I] is equal to S[j], the case can be divided into two kinds:

  • ifS[i] == s[j], so as long asS[i+1] toS[j-1]Is a string of subroutines,S[i] 至 S[j]That’s a string of subroutines; ifS [I + 1] to [S] j - 1Is not a subrine string, thenS [j] [I] to SIt’s not a subroutine
  • ifS[i] ! = S[j], thenS [j] [I] to SIt must not be a subroutine

Thus write the state transition equation:

if(S[i] == S[j]) dp[i][j] = dp[i+1][j-1]

if(S[i] ! = S[j]) dp[i][j] = 0

Boundary conditions: dp [I] [I] = 1, dp [I] [I + 1) = (S [I] [I + 1) = = S)? 1:0

Note that some states may never be transferred, such as fixing I and then enumerating j from 2

  • dp[0][2] => dp[1][1]If initialized, you can find ☑️
  • dp[0][3] => dp[1][2] If initialized, you can find ☑️
  • dp[0][4] => dp[1][3] Uninitialized, cannot find ❌

And no matter what we do, we can’t transfer this state, so we have to come up with new enumerations:

  • By recursively writing from the edge of the principle, notice that the edge represents a substring of length 1 and 2, and each time the substring length is subtracted by 1, so we can enumerate by the length of the substring and the initial position!
  • Enumerating all substrings of length 3 the first time, enumerating all substrings of length 4 the second time…

Enumerating the length L, then enumerating the left endpoint I, so that the right endpoint I + L -1 can also be obtained directly.

Code implementation:

#include <cstdio>
#include <cstring>

const int maxn = 1010;
char S[maxn];
int dp[maxn][maxn];

int main(a)
{
  gets(S);
  int len = strlen(S), ans = 1;
  memset(dp, 0.sizeof(dp));
  / / boundary
  for(int i = 0; i < len; i++) {
    dp[i][i] = 1;
    if(i < len - 1) {
      if(S[i] == S[i+1]) {
        dp[i][i+1] = 1;
        ans = 2;	// Pay attention to the current maximum callback substring length when initializing}}}// State transition equation
  for(int L = 3; L <= len; L++) {	// Enumeration length
    for(int i = 0; i + L - 1 < len; i++) {	// Enumerate the start endpoint
      int j = i + L - 1;	/ / right endpoints
      if(S[i] == S[j] && dp[i+1][j- 1] = =1) {
        dp[i][j] = 1;
        ans = L;	/ / update}}}printf("%d\n", ans);
  return 0;
}
Copy the code