[CF314B](Sereja and Periods)

• 題意

定義[x,n]為n個字元串x首尾相接

給你兩個字元串w=[a,b],q=[c,d];

求一個數ans

使得[ans,q]為w的子串,并要求最大化ans

• solution

暴力求解

就是aaaaaaaaa(b個a)中找有幾個c

關鍵兩點:

1.每個a是重複出現的

2.aa中可能還會出現關鍵字元(繼續比對),是以每個a串的比對不是一樣的,要麼找循環節,要麼像我一樣仍然枚舉b但加速比對過程

考慮到字元串長度不大,讓我們造兩個數組cnt[..],next[..]

\(cnt_i\)表示從\(c_i\)(注意是c串)開始比對

把a串比對一遍後,比對了幾個c串

\(next_i\)表示\(c_i\)(同樣是c串)開始比對

把a串掃一遍後比對到c串的哪一位

這裡有點kmp的思路,即在模式串上記下一次從哪裡開始比對

那麼我們從1掃到b

每次跳next,答案加cnt

next,cnt就能概括所有比對情況,是以我們用next,cnt省略每個a串(每個a串從頭掃到尾以比對b串)的比對過程

• code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#define N 205
using namespace std;
string s1,s2;
int a,b;
int nxt[N],cnt[N];
int main(){
  scanf("%d%d",&a,&b);
  cin>>s1>>s2;
  for(int i=0;i<s2.size();i++){
     int pos=i;
     for(int r=0;r<s1.size();r++){
        if(s2[pos]==s1[r]){
          pos++;
          if(pos==s2.size())cnt[i]++,pos=0;
          }
        }
     nxt[i]=pos;
     }
  int ans=0;
  int poss=0;
  for(int i=1;i<=a;i++)ans+=cnt[poss],poss=nxt[poss];
  cout<<ans/b;
}
           

轉載于:https://www.cnblogs.com/stepsys/p/10387841.html