HDU 6194 string string string （SAM）

Description

Uncle Mao is a wonderful ACMER. One day he met an easy problem, but Uncle Mao was so lazy that he left the problem to you. I hope you can give him a solution.

Given a string s, we define a substring that happens exactly k times as an important string, and you need to find out how many substrings which are important strings.

Input

The first line contains an integer T (T≤100) implying the number of test cases.

For each test case, there are two lines:

the first line contains an integer k (k≥1) which is described above;

the second line contain a string s (length(s)≤10^5).

Output

For each test case, print the number of the important substrings in a line.

Sample Input

2
2
abcabc
3
abcabcabcabc

Sample Output

6
9

题意

询问字符串 $s$ 中恰好出现 $k$ 次的子串有多少个。

思路

和 HDU 4641 一样的思路。

区间减法计算 [至少出现 $k$ 次的结果] 减去 [至少出现 $k+1$ 次的结果] 即为 [恰好出现 $k$ 次的结果]

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef __int64 LL;
const int maxn = 2e5 + 10;
LL ans;
int K;

struct SAM
{
    int next[maxn][26];
    int pre[maxn], step[maxn];
    int last, id;
    int num1[maxn], num2[maxn];
    void init()
    {
        last = id = 0;
        memset(next[0], -1, sizeof(next[0]));
        pre[0] = -1;
        step[0] = 0;
    }
    void insert(int c)
    {
        int p = last, np = ++id;
        step[np] = step[p] + 1;
        memset(next[np], -1, sizeof(next[np]));
        num1[np] = num2[np] = 0;

        while (p != -1 && next[p][c] == -1)
            next[p][c] = np, p = pre[p];
        if (p == -1)
            pre[np] = 0;
        else
        {
            int q = next[p][c];
            if (step[q] != step[p] + 1)
            {
                int nq = ++id;
                memcpy(next[nq], next[q], sizeof(next[q]));
                num1[nq] = num1[q];
                num2[nq] = num2[q];
                step[nq] = step[p] + 1;
                pre[nq] = pre[q];
                pre[np] = pre[q] = nq;
                while (p != -1 && next[p][c] == q)
                    next[p][c] = nq, p = pre[p];
            }
            else
                pre[np] = q;
        }
        last = np;

        /* diy */
        bool f1 = false, f2 = false;
        while (np != -1 && (!f1 || !f2))
        {
            if (!f1 && num1[np] < K)
            {
                num1[np]++;
                if (num1[np] == K)
                {
                    ans += step[np] - step[pre[np]];
                    f1 = true;
                }
            }
            if (!f2 && num2[np] < K + 1)
            {
                num2[np]++;
                if (num2[np] == K + 1)
                {
                    ans -= step[np] - step[pre[np]];
                    f2 = true;
                }
            }
            np = pre[np];
        }
        /* end diy */
    }
} sam;

char str[maxn];
LL get_ans()
{
    sam.init();
    ans = 0;
    int len = strlen(str);
    for (int i = 0; i < len; i++)
        sam.insert(str[i] - 'a');
    return ans;
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9')
        ;
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}
template <class T>
inline void print_d(T x)
{
    if (x > 9)
    {
        print_d(x / 10);
    }
    putchar(x % 10 + '0');
}

int main()
{
    int T;
    scan_d(T);
    while (T--)
    {
        scan_d(K);
        gets(str);
        print_d(get_ans());
        putchar('\n');
    }
    return 0;
}