結果

問題 No.1695 Mirror Mirror
ユーザー LayCurseLayCurse
提出日時 2021-10-01 22:47:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 16,295 bytes
コンパイル時間 2,860 ms
コンパイル使用メモリ 227,208 KB
実行使用メモリ 18,900 KB
最終ジャッジ日時 2023-09-26 21:15:43
合計ジャッジ時間 10,597 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
9,528 KB
testcase_01 AC 3 ms
9,560 KB
testcase_02 AC 3 ms
9,540 KB
testcase_03 AC 3 ms
9,696 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 4 ms
9,540 KB
testcase_07 AC 3 ms
9,628 KB
testcase_08 AC 3 ms
9,572 KB
testcase_09 AC 3 ms
9,740 KB
testcase_10 AC 3 ms
9,620 KB
testcase_11 AC 3 ms
9,508 KB
testcase_12 AC 4 ms
9,512 KB
testcase_13 AC 3 ms
9,536 KB
testcase_14 AC 4 ms
9,532 KB
testcase_15 AC 3 ms
9,524 KB
testcase_16 AC 3 ms
9,504 KB
testcase_17 AC 3 ms
9,516 KB
testcase_18 AC 3 ms
9,596 KB
testcase_19 AC 3 ms
9,568 KB
testcase_20 AC 3 ms
9,512 KB
testcase_21 AC 198 ms
18,852 KB
testcase_22 AC 209 ms
18,900 KB
testcase_23 AC 103 ms
18,396 KB
testcase_24 AC 111 ms
18,444 KB
testcase_25 AC 58 ms
15,136 KB
testcase_26 AC 3 ms
9,524 KB
testcase_27 AC 3 ms
9,652 KB
testcase_28 AC 5 ms
9,944 KB
testcase_29 WA -
testcase_30 AC 145 ms
15,620 KB
testcase_31 AC 277 ms
17,792 KB
testcase_32 AC 115 ms
11,180 KB
testcase_33 AC 186 ms
18,356 KB
testcase_34 AC 145 ms
13,392 KB
testcase_35 AC 178 ms
17,052 KB
testcase_36 AC 138 ms
18,632 KB
testcase_37 AC 190 ms
12,636 KB
testcase_38 AC 157 ms
17,092 KB
testcase_39 AC 104 ms
12,324 KB
testcase_40 AC 106 ms
17,888 KB
testcase_41 AC 138 ms
18,564 KB
testcase_42 AC 159 ms
18,584 KB
testcase_43 AC 165 ms
15,284 KB
testcase_44 AC 134 ms
16,540 KB
testcase_45 AC 82 ms
15,044 KB
testcase_46 AC 143 ms
15,928 KB
testcase_47 AC 165 ms
15,760 KB
testcase_48 AC 208 ms
18,356 KB
testcase_49 AC 179 ms
18,616 KB
testcase_50 AC 6 ms
10,100 KB
testcase_51 AC 6 ms
10,188 KB
testcase_52 AC 5 ms
9,888 KB
testcase_53 AC 5 ms
10,108 KB
testcase_54 AC 5 ms
9,884 KB
testcase_55 AC 86 ms
14,920 KB
testcase_56 AC 84 ms
16,300 KB
testcase_57 AC 83 ms
15,224 KB
testcase_58 AC 186 ms
17,600 KB
testcase_59 AC 174 ms
16,192 KB
testcase_60 AC 92 ms
15,204 KB
testcase_61 AC 65 ms
12,760 KB
testcase_62 WA -
testcase_63 WA -
testcase_64 AC 3 ms
9,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
template<class T> struct cLtraits_identity{
  using type = T;
}
;
template<class T> using cLtraits_try_make_signed =
  typename conditional<
    is_integral<T>::value,
    make_signed<T>,
    cLtraits_identity<T>
    >::type;
template <class S, class T> struct cLtraits_common_type{
  using tS = typename cLtraits_try_make_signed<S>::type;
  using tT = typename cLtraits_try_make_signed<T>::type;
  using type = typename common_type<tS,tT>::type;
}
;
void*wmem;
char memarr[96000000];
template<class S, class T> inline auto min_L(S a, T b)
-> typename cLtraits_common_type<S,T>::type{
  return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;
}
template<class S, class T> inline auto max_L(S a, T b)
-> typename cLtraits_common_type<S,T>::type{
  return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;
}
struct Rand{
  unsigned x;
  unsigned y;
  unsigned z;
  unsigned w;
  Rand(void){
    x=123456789;
    y=362436069;
    z=521288629;
    w=(unsigned)time(NULL);
  }
  Rand(unsigned seed){
    x=123456789;
    y=362436069;
    z=521288629;
    w=seed;
  }
  inline unsigned get(void){
    unsigned t;
    t = (x^(x<<11));
    x=y;
    y=z;
    z=w;
    w = (w^(w>>19))^(t^(t>>8));
    return w;
  }
  inline double getUni(void){
    return get()/4294967296.0;
  }
  inline int get(int a){
    return (int)(a*getUni());
  }
  inline int get(int a, int b){
    return a+(int)((b-a+1)*getUni());
  }
  inline long long get(long long a){
    return(long long)(a*getUni());
  }
  inline long long get(long long a, long long b){
    return a+(long long)((b-a+1)*getUni());
  }
  inline double get(double a, double b){
    return a+(b-a)*getUni();
  }
  inline int getExp(int a){
    return(int)(exp(getUni()*log(a+1.0))-1.0);
  }
  inline int getExp(int a, int b){
    return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0);
  }
}
;
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(char &c){
  int i;
  for(;;){
    i = my_getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c = i;
}
inline int rd(char c[]){
  int i;
  int sz = 0;
  for(;;){
    i = my_getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = my_getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
template<class T, class U> inline T GCD_L(T a, U b){
  T r;
  while(b){
    r=a;
    a=b;
    b=r%a;
  }
  return a;
}
template<class S, class T> inline int arrcmp(int As, S A[], int Bs, T B[]){
  int i;
  for(i=0;;i++){
    if(i==As && As==Bs){
      break;
    }
    if(i==As){
      return -1;
    }
    if(i==Bs){
      return 1;
    }
    if(A[i] < B[i]){
      return -1;
    }
    if(A[i] > B[i]){
      return 1;
    }
  }
  return 0;
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
template<class T> int KMP(T A[], int As, T B[], int Bs, int res[] = NULL, int *fail = (int*)wmem){
  int i;
  int k;
  int cnt = 0;
  k = fail[0] = -1;
  for(i=(0);i<(Bs);i++){
    while(k>=0 && B[k]!=B[i]){
      k = fail[k];
    }
    fail[i+1] = ++k;
  }
  if(res != NULL){
    for(i=(0);i<(As);i++){
      res[i] = 0;
    }
  }
  k = 0;
  for(i=(0);i<(As);i++){
    while(k >= 0 && B[k] != A[i]){
      k = fail[k];
    }
    k++;
    if(k == Bs){
      cnt++;
      if(res != NULL){
        res[i-Bs+1] = 1;
      }
      k = fail[k];
    }
  }
  return cnt;
}
template<class T, class S> int KMP(T A[], int As, T B[], int Bs, S res[], int *fail = (int*)wmem){
  int i;
  int k;
  int cnt = 0;
  k = fail[0] = -1;
  for(i=(0);i<(Bs);i++){
    while(k>=0 && B[k]!=B[i]){
      k = fail[k];
    }
    fail[i+1] = ++k;
  }
  if(res != NULL){
    for(i=(0);i<(As);i++){
      res[i] = 0;
    }
  }
  k = 0;
  for(i=(0);i<(As);i++){
    while(k >= 0 && B[k] != A[i]){
      k = fail[k];
    }
    k++;
    if(k == Bs){
      cnt++;
      if(res != NULL){
        res[i-Bs+1] = 1;
      }
      k = fail[k];
    }
  }
  return cnt;
}
#define ROLLING_HASH_MOD (2305843009213693951ULL)
#define ROLLING_HASH_PRIMITIVE_ROOT (3)
#define ROLLING_HASH_MAX_MEMORY (2000000)
int ROLLING_HASH_MEM;
unsigned long long ROLLING_HASH_BASE;
unsigned long long ROLLING_HASH_IBASE;
unsigned long long*ROLLING_HASH_PW = NULL;
unsigned long long*ROLLING_HASH_IPW = NULL;
inline unsigned long long rollingHash61_mul(unsigned long long a, unsigned long long b){
  __uint128_t r = (__uint128_t) a * b;
  a = (r >> 61) + (r & ROLLING_HASH_MOD);
  if(a >= ROLLING_HASH_MOD){
    a -= ROLLING_HASH_MOD;
  }
  return a;
}
inline unsigned long long rollingHash61_pow(unsigned long long a, unsigned long long b){
  unsigned long long r = 1;
  for(;;){
    if(b&1){
      r = rollingHash61_mul(r, a);
    }
    if(b==0){
      break;
    }
    b >>= 1;
    a = rollingHash61_mul(a, a);
  }
  return r;
}
void rollingHashInit(){
  int i;
  Rand rnd;
  unsigned long long x;
  for(i=(0);i<(20);i++){
    rnd.get(2);
  }
  do{
    x = rnd.get(1.0, (double)(ROLLING_HASH_MOD-2));
  }
  while(GCD_L(x, ROLLING_HASH_MOD-1)!= 1);
  ROLLING_HASH_BASE = rollingHash61_pow(ROLLING_HASH_PRIMITIVE_ROOT, x);
  ROLLING_HASH_IBASE = rollingHash61_pow(ROLLING_HASH_BASE, ROLLING_HASH_MOD - 2);
}
void rollingHash_expand(int k){
  int i;
  if(ROLLING_HASH_MEM >= k){
    return;
  }
  ROLLING_HASH_MEM =max_L(2 * ROLLING_HASH_MEM, k);
  assert(ROLLING_HASH_MEM <= 2 * ROLLING_HASH_MAX_MEMORY);
  ROLLING_HASH_PW = (unsigned long long*) realloc(ROLLING_HASH_PW, ROLLING_HASH_MEM * sizeof(unsigned long long));
  ROLLING_HASH_IPW = (unsigned long long*) realloc(ROLLING_HASH_IPW, ROLLING_HASH_MEM * sizeof(unsigned long long));
  ROLLING_HASH_PW[0] = 1;
  for(i=(1);i<(ROLLING_HASH_MEM);i++){
    ROLLING_HASH_PW[i] = rollingHash61_mul(ROLLING_HASH_PW[i-1], ROLLING_HASH_BASE);
  }
  ROLLING_HASH_IPW[0] = 1;
  for(i=(1);i<(ROLLING_HASH_MEM);i++){
    ROLLING_HASH_IPW[i] = rollingHash61_mul(ROLLING_HASH_IPW[i-1], ROLLING_HASH_IBASE);
  }
}
struct rollingHash{
  long long len;
  unsigned long long hs;
  template<class T> void set(int N, T A[]){
    int i;
    long long tmp;
    hs = 0;
    len = N;
    rollingHash_expand(N);
    for(i=(0);i<(N);i++){
      tmp = A[i] % ((long long)ROLLING_HASH_MOD);
      if(tmp < 0){
        tmp += ROLLING_HASH_MOD;
      }
      hs += rollingHash61_mul(tmp, ROLLING_HASH_PW[i]);
      if(hs >= ROLLING_HASH_MOD){
        hs -= ROLLING_HASH_MOD;
      }
    }
  }
  template<class S, class T> void change(long long ind, S bef, T aft){
    long long tmp1;
    long long tmp2;
    tmp1 = bef % ((long long)ROLLING_HASH_MOD);
    tmp2 = aft % ((long long)ROLLING_HASH_MOD);
    tmp1 = tmp2 - tmp1;
    if(tmp1 < 0){
      tmp1 += ROLLING_HASH_MOD;
    }
    if(tmp1 < 0){
      tmp1 += ROLLING_HASH_MOD;
    }
    if(tmp1 >= ROLLING_HASH_MOD){
      tmp1 -= ROLLING_HASH_MOD;
    }
    if(ind+1 <= ROLLING_HASH_MAX_MEMORY || ind+1 >= ROLLING_HASH_MEM){
      rollingHash_expand(ind+1);
      hs += rollingHash61_mul(tmp1, ROLLING_HASH_PW[ind]);
    }
    else{
      hs += rollingHash61_mul(tmp1, rollingHash61_pow(ROLLING_HASH_BASE, ind));
    }
    if(hs >= ROLLING_HASH_MOD){
      hs -= ROLLING_HASH_MOD;
    }
  }
  void push_front(rollingHash a){
    if(a.len + 1 <= ROLLING_HASH_MAX_MEMORY || a.len + 1 >= ROLLING_HASH_MEM){
      rollingHash_expand(a.len + 1);
      hs = rollingHash61_mul(hs, ROLLING_HASH_PW[a.len]);
    }
    else{
      hs = rollingHash61_mul(hs, rollingHash61_pow(ROLLING_HASH_BASE, a.len));
    }
    hs += a.hs;
    if(hs >= ROLLING_HASH_MOD){
      hs -= ROLLING_HASH_MOD;
    }
    len += a.len;
  }
  void push_back(rollingHash a){
    if(len + 1 <= ROLLING_HASH_MAX_MEMORY || len + 1 >= ROLLING_HASH_MEM){
      rollingHash_expand(len + 1);
      hs += rollingHash61_mul(a.hs, ROLLING_HASH_PW[len]);
    }
    else{
      hs += rollingHash61_mul(a.hs, rollingHash61_pow(ROLLING_HASH_BASE, len));
    }
    if(hs >= ROLLING_HASH_MOD){
      hs -= ROLLING_HASH_MOD;
    }
    len += a.len;
  }
  void pop_front(rollingHash a){
    if(hs >= a.hs){
      hs -= a.hs;
    }
    else{
      hs = hs + ROLLING_HASH_MOD - a.hs;
    }
    if(a.len + 1 <= ROLLING_HASH_MAX_MEMORY || a.len + 1 >= ROLLING_HASH_MEM){
      rollingHash_expand(a.len + 1);
      hs = rollingHash61_mul(hs, ROLLING_HASH_IPW[a.len]);
    }
    else{
      hs = rollingHash61_mul(hs, rollingHash61_pow(ROLLING_HASH_IBASE, a.len));
    }
    len -= a.len;
  }
  void pop_back(rollingHash a){
    unsigned long long tmp;
    if(len + 1 <= ROLLING_HASH_MAX_MEMORY || len + 1 >= ROLLING_HASH_MEM){
      rollingHash_expand(len + 1);
      tmp = rollingHash61_mul(a.hs, ROLLING_HASH_PW[len]);
    }
    else{
      tmp = rollingHash61_mul(a.hs, rollingHash61_pow(ROLLING_HASH_BASE, len));
    }
    if(hs >= tmp){
      hs -= tmp;
    }
    else{
      hs = hs + ROLLING_HASH_MOD - tmp;
    }
    len -= a.len;
  }
  bool operator==(const rollingHash a){
    return len == a.len && hs == a.hs;
  }
  bool operator!=(const rollingHash a){
    return len != a.len || hs != a.hs;
  }
}
;
template<class T> rollingHash calcRollingHash(int N, T A[]){
  rollingHash res;
  res.set(N, A);
  return res;
}
struct rollingHashSubarrays{
  unsigned long long*hs;
  int mem;
  int len;
  void set(){
    hs = NULL;
    mem = len = 0;
  }
  void free(){
    if(mem){
      delete[] hs;
    }
  }
  void expand(int k){
    if(mem >= k){
      return;
    }
    free();
    mem =max_L(2*mem, k);
    hs = new unsigned long long[mem];
  }
  template<class T> void set(int N, T A[]){
    int i;
    long long tmp;
    if(N <= 0){
      return;
    }
    rollingHash_expand(N);
    expand(N);
    len = N;
    tmp = A[0] % ((long long)ROLLING_HASH_MOD);
    if(tmp < 0){
      tmp += ROLLING_HASH_MOD;
    }
    hs[0] = tmp;
    for(i=(1);i<(N);i++){
      tmp = A[i] % ((long long)ROLLING_HASH_MOD);
      if(tmp < 0){
        tmp += ROLLING_HASH_MOD;
      }
      hs[i] = hs[i-1] + rollingHash61_mul(tmp, ROLLING_HASH_PW[i]);
      if(hs[i] >= ROLLING_HASH_MOD){
        hs[i] -= ROLLING_HASH_MOD;
      }
    }
  }
  rollingHash get_len(int s, int len){
    unsigned long long x;
    rollingHash res;
    res.len = len;
    rollingHash_expand(s+1);
    if(s == 0){
      res.hs = hs[len-1];
    }
    else{
      if(hs[s+len-1] >= hs[s-1]){
        res.hs = hs[s+len-1] - hs[s-1];
      }
      else{
        res.hs = hs[s+len-1] + ROLLING_HASH_MOD - hs[s-1];
      }
      res.hs = rollingHash61_mul(res.hs, ROLLING_HASH_IPW[s]);
    }
    return res;
  }
  rollingHash get(int a, int b){
    return get_len(a, b - a + 1);
  }
  rollingHashSubarrays(){
    set();
  }
  ~rollingHashSubarrays(){
    free();
  }
}
;
int N;
int M;
char S[500000+2];
char T[500000+2];
char tt[500000+2];
int dp[500000+2];
rollingHashSubarrays arr1;
rollingHashSubarrays arr2;
int solve(){
  int i;
  int j;
  int k;
  int m;
  int e;
  if(M%2){
    return 1073709056;
  }
  m = M / 2;
  for(i=(0);i<(m);i++){
    if(T[i] != T[M-1-i]){
      return 1073709056;
    }
  }
  if(m <= N){
    for(i=(0);i<(m);i++){
      tt[i] = S[i];
    }
    for(i=(0);i<(m);i++){
      tt[m+i] = S[m-1-i];
    }
    if(arrcmp(M,T,M,tt)==0){
      return 1;
    }
  }
  for(i=(0);i<(m+1);i++){
    dp[i] = 1073709056;
  }
  for(i=(0);i<(N);i++){
    tt[i] = S[N-1-i];
  }
  int KrdatlYV;
  int ao_dF3pO;
  int tU__gIr_;
  KrdatlYV = 0;
  ao_dF3pO = m;
  while(KrdatlYV < ao_dF3pO){
    if((KrdatlYV + ao_dF3pO)%2==0){
      tU__gIr_ = (KrdatlYV + ao_dF3pO) / 2;
    }
    else{
      tU__gIr_ = (KrdatlYV + ao_dF3pO + 1) / 2;
    }
    if(KMP(S,N,T,tU__gIr_)){
      KrdatlYV = tU__gIr_;
    }
    else{
      ao_dF3pO = tU__gIr_ - 1;
    }
  }
  k =ao_dF3pO;
  for(i=(0);i<(k);i++){
    chmin(dp[i+1], 2);
  }
  int YREPHmFM;
  int jZyWAPpY;
  int jbtyPBGc;
  YREPHmFM = 0;
  jZyWAPpY = m;
  while(YREPHmFM < jZyWAPpY){
    if((YREPHmFM + jZyWAPpY)%2==0){
      jbtyPBGc = (YREPHmFM + jZyWAPpY) / 2;
    }
    else{
      jbtyPBGc = (YREPHmFM + jZyWAPpY + 1) / 2;
    }
    if(KMP(tt,N,T,jbtyPBGc)){
      YREPHmFM = jbtyPBGc;
    }
    else{
      jZyWAPpY = jbtyPBGc - 1;
    }
  }
  k =jZyWAPpY;
  for(i=(0);i<(k);i++){
    chmin(dp[i+1], 1);
  }
  for(i=(0);i<(min_L(m, N));i++){
    if(S[i] != T[i]){
      break;
    }
    if(i==N-1){
      chmin(dp[i+1], 0);
    }
    else{
      chmin(dp[i+1], 1);
    }
  }
  for(i=(0);i<(m);i++){
    tt[i] = T[m-1-i];
  }
  arr1.set(m, T);
  arr2.set(m, tt);
  e = 1;
  for(i=(0);i<(m);i++){
    int zT28qSmp;
    int aTqQ6rt8;
    int X9Iss0pP;
    zT28qSmp = 0;
    aTqQ6rt8 =min_L(i, m-i);
    while(zT28qSmp < aTqQ6rt8){
      if((zT28qSmp + aTqQ6rt8)%2==0){
        X9Iss0pP = (zT28qSmp + aTqQ6rt8) / 2;
      }
      else{
        X9Iss0pP = (zT28qSmp + aTqQ6rt8 + 1) / 2;
      }
      if( arr1.get_len(i,X9Iss0pP) == arr2.get_len(m-i,X9Iss0pP) ){
        zT28qSmp = X9Iss0pP;
      }
      else{
        aTqQ6rt8 = X9Iss0pP - 1;
      }
    }
    k =aTqQ6rt8;
    chmax(e, i+1);
    while(e <= i+k){
      chmin(dp[e], dp[i] + 1);
      e++;
    }
  }
  return max_L(2, dp[m]);
}
int main(){
  wmem = memarr;
  {
    rollingHashInit();
  }
  int res = 1073709056;
  rd(N);
  rd(M);
  rd(S);
  rd(T);
  chmin(res, solve());
  reverse(S,S+N);
  reverse(T,T+M);
  chmin(res, solve());
  if(res==1073709056){
    wt_L(-1);
    wt_L('\n');
  }
  else{
    wt_L(res);
    wt_L('\n');
  }
  return 0;
}
// cLay version 20210926-1

// --- original code ---
// int N, M;
// char S[5d5+2], T[], tt[];
// int dp[];
// 
// rollingHashSubarrays arr1, arr2;
// 
// int solve(){
//   int i, j, k, m, e;
// 
//   if(M%2) return int_inf;
//   m = M / 2;
//   rep(i,m) if(T[i] != T[M-1-i]) return int_inf;
// 
//   if(m <= N){
//     rep(i,m) tt[i] = S[i];
//     rep(i,m) tt[m+i] = S[m-1-i];
//     if(arrcmp(M,T,M,tt)==0) return 1;
//   }
// 
//   rep(i,m+1) dp[i] = int_inf;
// 
//   rep(i,N) tt[i] = S[N-1-i];
// 
//   k = bsearch_max[int,k,0,m](KMP(S,N,T,k));
//   rep(i,k) dp[i+1] <?= 2;
//   k = bsearch_max[int,k,0,m](KMP(tt,N,T,k));
//   rep(i,k) dp[i+1] <?= 1;
//   rep(i,min(m,N)){
//     if(S[i] != T[i]) break;
//     dp[i+1] <?= if[i==N-1, 0, 1];
//   }
// 
//   rep(i,m) tt[i] = T[m-1-i];
//   arr1.set(m, T);
//   arr2.set(m, tt);
//   e = 1;
// 
//   rep(i,m){
//     k = bsearch_max[int,k,0,min(i,m-i)]( arr1.get_len(i,k) == arr2.get_len(m-i,k) );
//     e >?= i+1;
//     while(e <= i+k) dp[e] <?= dp[i] + 1, e++;
//   }
// 
//   // wt(dp(m+1));
//   return max(2,dp[m]);
// }
// 
// {
//   int res = int_inf;
//   rd(N,M,S,T);
//   res <?= solve();
//   reverse(S,S+N);
//   reverse(T,T+M);
//   res <?= solve();
//   wt(if[res==int_inf, -1, res]);
// }
0