注意， 题目求的是数量的个数

渣渣表示只想到了暴力做法，O(n^2)， 50%案例 TLE
思路：
第一步： Kmp求出next数组
第二步： 定义k = next[i], 判断当前下标j, 长度为k的前缀是否符合条件, 符合的话num[j]++

import java.io.*;
class Main{
    static int mod = (int)1e9 + 7;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter  log = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception{
        int m = Integer.valueOf(read.readLine());
        while(m -- > 0){
            char[] p = (" " + read.readLine()).toCharArray();
            int n = p.length - 1;
            int[] ne = new int[n + 1];
            int[] num = new int[n + 1];
            //第一步， KMP求出ne数组
            for(int i = 0, j = 2; j <= n; j++){
                while(i != 0 && p[j] != p[i + 1]) i = ne[i];
                if(p[j] == p[i + 1]) i++;
                ne[j] = i;
            }
            long res = 1;
            //第二步， 通过ne数组计算 num[j]
            for(int j = 1; j <= n; j++){
                int k = ne[j];
                while(k != 0){
                    if(k <= j / 2) num[j]++;
                    k = ne[k];
                }
                res = res * (num[j] + 1) % mod;
            }
            log.write(res + "\n");

        }
        log.flush();
    }
}

方法二， 一遍KMP求解， 参考网上资料的， O(n) AC
思路：
类似next数组， 定义cnt数组,
cnt[]就是到j所以满足就是前缀也是后缀的子串数,cnt[j]=cnt[next[j]]+1;
然后，用求next的方法，顺便约束( k + 1 > j / 2),num[j]=cnt[k];

import java.io.*;
class Main{
    static int mod = (int)1e9 + 7;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter  log = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception{
        int m = Integer.valueOf(read.readLine());
        while(m -- > 0){
            char[] p = (" " + read.readLine()).toCharArray();
            int n = p.length - 1;
            int[] ne = new int[n + 1];
            int[] num = new int[n + 1];
            //cnt[],就是到j所以满足就是前缀也是后缀的子串数,cnt[j]=cnt[next[j]]+1;
            int[] cnt = new int[n + 1];
            cnt[1] = 1;
            long res = 1;

            for(int i = 0, j = 2, k = 0; j <= n; j++){
                //第一步， KMP求出ne数组
                while(i != 0 && p[j] != p[i + 1]) i = ne[i];
                if(p[j] == p[i + 1]) i++;
                ne[j] = i;
                //第二步， KMP求出 cnt 数组
                cnt[j] = cnt[ne[j]] + 1;
                while(k != 0 && (p[k + 1] != p[j] || (k + 1 > j / 2))) k = ne[k];
                if(p[k + 1] == p[j]) k++;
                num[j] = cnt[k] + 1;
                res = res * num[j] % mod;
            }
            log.write(res + "\n");

        }
        log.flush();
    }
}