标签归档:KMP

HDU – 3613 Best Reward

Best Reward

扩展kmp与回文串问题

在扩展kmp中,设模式串为P1,目标串为P2
extend[i]表示P2[i]~P2[n]与P1的最长公共前缀长度.

设原串为P,将其倒置为S.
以P为模式串执行一遍e-KMP,得到extend1数组,P的前缀是回文串的条件是extend1[i]+i=length(S)
以S为模式串执行一遍e-KMP,得到extend2数组,P的后缀是回文串的条件是extend2[i]+i=length(P)
画出图更好理解.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

int Next[500001];
int extend1[500010];
int extend2[500010];
char p[500001];
char s[500001];
int value[500001];
void eKMP_pre(char x[],int m,int next[]){
  next[0]=m;
  int j=0;
  while(j+1<m&&x[j]==x[j+1]) j++;
  next[1]=j;
  int k=1;
  for(int i=2;i<m;++i){
    int p=next[k]+k-1;
    int L=next[i-k];
    if(i+L-1<p) next[i]=L;
    else{
      j=max(0,p-i+1);
      while(i+j<m&&x[i+j]==x[j]) j++;
      next[i]=j;
      k=i;
    }
  }
}

void eKMP(char x[],int m,char y[],int n,int next[],int extend[]){
  eKMP_pre(x,m,next);
  int j=0;
  while(j<n&&j<m&&x[j]==y[j]) j++;
  extend[0]=j;
  int k=0;
  for(int i=1;i<n;++i){
    int p=extend[k]+k-1;
    int L=next[i-k];
    if(i+L-1<p) extend[i]=L;
    else{
      j=max(0,p-i+1);
      while(i+j<n&&j<m&&y[i+j]==x[j]) j++;
      extend[i]=j;
      k=i;
    }
  }
}

int v[26];

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int kase=0;
  int n,T;
  scanf("%d",&T);
  while(T--){
    for(int i=0;i<26;++i){
      scanf("%d",&v[i]);
    }
    scanf("%s",p);
    int len=strlen(p);
    int k=0;
    for(int i=len-1;i>=0;i--){
        s[k]=p[i];
        value[k]=v[s[k]-'a'];
        if(k)  value[k]=value[k]+value[k-1];
        k++;
    }
    eKMP(p,len,s,len,Next,extend1);
    eKMP(s,len,p,len,Next,extend2);
    int ans=-INF;
    for(int i=1;i<len;++i){
      int temp=0;
      if(i+extend1[i]==len){
          temp+=value[i+extend1[i]-1]-value[i-1];
          if(extend1[i]+extend2[extend1[i]]==len){
            temp+=value[i-1];
          }
      }
      else{
         if(len-i+extend2[len-i]==len){
           temp+=value[i-1];
         }
      }
      ans=max(ans,temp);
    }
    printf("%d\n",ans);
  }

  return 0;
}

HDU – 1358 Period

Period

KMP算法和周期性字符串.

i-next[i] 为最小循环元长度,i/(i-next[i])为最大循环次数.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

int Next[1000010];
char p[1000010];

void kmp_pre(char x[],int m,int next[]){
    int i,j;
    j=next[0]=-1;
    i=0;
    while(i<m){
      while(-1!=j&&x[i]!=x[j]) j=next[j];
      next[++i]=++j;
    }
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int kase=0;
  int n;
  while(cin>>n&&n){
    scanf("%s",p);
    kmp_pre(p,n,Next);
    int i=n;
    printf("Test case #%d\n",++kase);
    for(int i=2;i<=n;++i){
        if(i/(i-Next[i])>1&&i%(i-Next[i])==0){
            printf("%d %d\n",i,i/(i-Next[i]));
        }
    }
    printf("\n");
  }

  return 0;
}