[NOI2014]动物园 题解

/**
 * @Author: Mingyu Li
 * @Date:   2019-03-16T16:11:25+08:00
 * @Email:  class11limingyu@126.com
 * @Filename: P2375.cpp
 * @Last modified by:   Mingyu Li
 * @Last modified time: 2019-03-16T20:44:23+08:00
 */

#include <bits/stdc++.h>
#define Go(i , x , y) for(register int i = x; i <= y; i++)
#define God(i , y , x) for(register int i = y; i >= x; i--)
typedef long long LL;
template < typename T > void sc(T& t) {
  char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();}
  while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x;
}
template < typename T , typename... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);}

const int N = 1000000 + 5;
char a[N];
int t , next[N] , cnt[N] , ans[N];
int main() {
  sc(t);
  while(t--) {
    memset(next , 0 , sizeof(next));
    memset(cnt , 0 , sizeof(cnt));
    memset(ans , 0 , sizeof(ans));
    scanf("%s" , (a+1));
    int n = strlen(a+1);
    LL mult = 1;
    next[1] = 0 , ans[1] = 1;
    Go(i , 2 ,  n) {
      int j = next[i-1];
      while(j && a[j+1] != a[i]) j = next[j];
      if(a[j+1] == a[i]) next[i] = j+1 , j++;
      else next[i] = 0;
      ans[i] = ans[j] + 1;
    }

    //Go(i , 1 , n) std::cerr << ans[i] << " ";
    //std::cerr << "\n";
    for(int i=2 , j=0; i <= n; i++) {
      while(j && a[j+1] != a[i]) j = next[j];
      if(a[j+1] == a[i]) ++j;
      while((j << 1) > i) j = next[j];
      mult = mult * (ans[j] + 1) % (LL)(1e9 + 7);
    }
    printf("%lld\n" , mult);
  }
  return 0;
}