SPOJ - PLSQUARE Palin Squar（hash+回文串）-白红宇

SPOJ - PLSQUARE Palin Squar（hash+回文串）

阅读量：7083 次

发布时间：2019-06-28

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

题意：给你一个n*n (n<=200)的字符串矩阵，问你每行每列都是回文串的最大的m*m的矩阵是多少

题解：首先答案不满足单调性，即m成立而m-1与m+1都却不一定成立，所以必须枚举答案确定现在的值是否成立，从大到小枚举就好

当枚举值为k时就转换为判断k是否为所求矩阵，判断时我们需要枚举每个点，（看从这个点开始是否向右向下都有连续k个回文串）

而我们可以分别找向右和向下，标记这个点向右或向下是否满足（从这个点开始是否向右向下都有连续k个回文串）

我们找向下时枚举每列每个向右k个字符是否为回文串

如果这个是回文，就在基础上加一否则基础就变成0（连续断掉），接着马上判断基础，大于k就在此位置前面k-1个位置标记为1

时间复杂度就是O（n^3），乘上前面的O（n）就过不了，但是我们可以预处理每个点向右，向下每个长度是否为回文串，这样就可以降O（n）的时间复杂度

预处理可以使用hash就是经典用法。但是一个更简单的方法就是dp，因为我们要找每段，则可以递归

4#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define sgn(x) (x<-eps? -1 :x
                  
                    0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))
                   
                    >b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const ll INF=1ll<<60;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=300;const ull seed=1313ull;ull base[Max],hashh[2][Max];//求字符串hash值（前缀与后缀）bool vis[2][Max][Max];//固定答案时保存是否为回文bool pal[Max][Max][2][Max];//每个位置向左与向下每个长度是否为回文串char str[Max][Max];void Init(int n){ base[0]=1ull; for(int i=1; i
                    
                     =ans)//此点左边ans个向下都是回文串 { vis[1][i][j-ans+1]=1; } ver++; if(!pal[j][i][0][ans])//断开了 { ver=0; } if(ver>=ans)//此点下边ans个向右都是回文串 { vis[0][j-ans+1][i]=1; } } } for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { if(vis[0][i][j]&vis[1][i][j]) return 1; } } return 0;}int Solve(int n){ for(int i=n; i>1; --i)//枚举结果 { if(Jud(i,n)) return i; } return 1;}int main(){ Init(Max); int n; while(~scanf("%d",&n)) { for(int i=1; i<=n; ++i) { scanf("%s",str[i]+1); str[i][0]='A'; } InitPal(n);//初始化每个点向右玉向下每个位置是否为回文串 printf("%d\n",Solve(n)); } return 0;}

转载于:https://www.cnblogs.com/zhuanzhuruyi/p/6250556.html

你可能感兴趣的文章

AI开发者福音！阿里云推出国内首个基于英伟达NGC的GPU优化容器