自动搬运

查看原文

来自洛谷，原作者为

	ZlycerQan **

搬运于2025-08-24 21:36:42，当前版本为作者最后更新于2017-08-09 15:53:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

/* luogu P2353 背单词

由于M很小

可以进行M次kmp

统计出M个前缀和

每次输出时把 M 个前缀和扫一遍

注意区间的开闭问题

由于r端点的串不包含在所查询的区间内

所以要减去当前模式串的长度

*/

#include <cstdio>
#include <cstring>

#define Max 1000090

void read (int &now)
{
    now = 0;
    register char word = getchar ();
    while (word > '9' || word < '0')
        word = getchar ();
    while (word >= '0' && word <= '9')
    {
        now = now * 10 + word - '0';
        word = getchar ();
    }
}

int __next[Max];

void Get_Next (char *line)
{
    __next[0] = -1;

    for (int pos_1 = 0, pos_2 = -1, Len = strlen (line); pos_1 < Len; )
        if (pos_2 == -1 || line[pos_1] == line[pos_2])
        {
            pos_1 ++;
            pos_2 ++;
            __next[pos_1] = pos_2;
        }
        else
            pos_2 = __next[pos_2];
    
}

int __sum[Max][Max / 100000 + 1];

void Kmp (char *line, char *__txt, int number)
{
    for (int Len_txt = strlen (__txt), Len = strlen (line), pos_1 = 0, pos_2 = 0; pos_1 <= Len_txt; )
    {
        if (pos_2 == -1 || __txt[pos_1] == line[pos_2])
        {
            pos_1 ++;
            pos_2 ++;
        }
        else
            pos_2 = __next[pos_2];
        if (pos_2 == Len)
        {
            __sum[pos_1][number] ++;
            pos_2 = __next[pos_2];
        }
    }
}

char __txt[Max];

int length[Max];
char line[Max];

int main (int argc, char *argv[])
{
    int N, M;
    
    read (N);
    read (M);
    
    scanf ("%s", __txt);
    
    int Len_txt = strlen (__txt);
    
    for (int i = 1; i <= N; i ++)
    {
        scanf ("%s", line);
        
        Get_Next (line);
        Kmp (line, __txt, i);
        
        length[i] = strlen (line);
    }
    
    for (int i = 1; i <= Len_txt; i ++) // 把每个模式串的前缀和分开存 
        for (int j = 1; j <= N; j ++)
            __sum[i][j] += __sum[i - 1][j];
    
    for (int i = 1, x, y, Answer; i <= M; i ++)
    {
        read (x);
        read (y);
        Answer = 0;
        
        for (int j = 1; j <= N; j ++)
            if (x - 1 <= y - length[j])
                Answer += __sum[y][j] - __sum[x + length[j] - 2][j];
    
        printf ("%d\n", Answer);
    }
    return 0;
}