Oulipo-白红宇

Oulipo

阅读量：795 次

发布时间：2023-02-26

本文共 1388 字，大约阅读时间需要 4 分钟。

为了解决问题，我们需要计算给定字符串W在较长字符串T中的出现次数。为了高效地完成这一任务，我们可以使用KMP算法，这是一种线性时间复杂度的字符串匹配算法，特别适合处理长文本。

方法思路

问题分析：我们需要找到字符串W在字符串T中的所有非重叠和重叠出现次数。由于T可能非常长，直接暴力匹配会导致效率低下，因此需要一个高效的算法。

KMP算法：KMP算法通过构建前缀函数数组来快速匹配字符串，避免回溯，提高效率。前缀函数数组记录在当前位置前缀的最大长度，使得在匹配失败时可以快速跳转到合适的位置继续匹配。

构建前缀函数：前缀函数数组的长度等于W的长度加1。通过遍历W，构建前缀函数数组，记录每个位置的最大前缀长度。

匹配过程：使用构建好的前缀函数数组，遍历T，匹配W的字符。每当找到一个匹配时，计数器加1，并更新当前位置以继续寻找下一个匹配。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int main() { int N; scanf("%d", &N); while (N--) { char P[10010], T[1000010]; int lenP, lenT; scanf("%s%s", P, T); lenP = strlen(P); lenT = strlen(T); if (lenP == 0) { printf("0\n"); continue; } if (lenT < lenP) { printf("0\n"); continue; } int next[lenP + 1]; int j = 0; for (int i = 1; i <= lenP; ++i) { while (j > 0 && P[j] != P[i]) { j = next[j]; } if (P[j] == P[i]) { j++; } next[i] = j; } int ans = 0, i = 1, j = 1; while (i <= lenT) { if (P[j] == T[i]) { if (j == lenP) { ans++; j = next[j] + 1; i++; } else { i++; j++; } } else { if (j == 1) { i++; } else { j = next[j - 1]; } } } printf("%d\n", ans); } return 0;}

代码解释

读取输入：首先读取测试用例的数量N，然后依次读取每个测试用例的字符串W和T。

前缀函数构建：构建前缀函数数组next，记录每个位置的最大前缀长度。通过遍历W，使用双指针技巧来构建前缀函数。

匹配过程：使用构建好的前缀函数数组，遍历T，匹配W的字符。每当找到一个匹配时，计数器加1，并更新当前位置以继续寻找下一个匹配。

输出结果：对于每个测试用例，输出匹配次数。

这种方法确保了在处理长字符串时的高效性，能够快速准确地统计字符串W在T中的出现次数。

转载地址：http://cbvfk.baihongyu.com/

你可能感兴趣的文章