题目大意
给定两个字符串S1, S2,求S1中包含多少个S2串。其中S1长度最大为 1000000, S2长度最大为10000。
题目分析
典型的字符串匹配问题,直接匹配显然会超时,考虑使用kmp算法。
需要注意的是,尽量减少求串长度的strlen的执行次数。
实现(c++)
#define _CRT_SECURE_NO_WARNINGS #define MAX_WORD_LEN 10005 #define MAX_TEXT_LEN 1000005 #include<stdio.h> #include<string.h> char gWord[MAX_WORD_LEN]; char gText[MAX_TEXT_LEN]; int gNext[MAX_WORD_LEN]; void GenerateNext(const char* sub_str, int* next, int len){ next[0] = 0; //next[i]表示sub_str[0, i]中最长相同前后缀的长度 for (int i = 1; i < len; i++){ int j = next[i - 1]; while (sub_str[j] != sub_str[i]){ //不断回溯,每次利用next数组来确定下一个需要判断的位置 if (j == 0){ j = -1; break; } j = next[j - 1]; } if (j < 0) next[i] = 0; else next[i] = j + 1; } } //返回母串中有多少个子串 int Kmp(char* mas_str, const char* sub_str, int* next, int len){ int count = 0; char* pos = mas_str; //母串中当前检查的位置 int i = 0; //子串中当前检查的位置 char* end = mas_str + strlen(mas_str); while (pos + len - i <= end){ while (i < len && *(pos + i) == sub_str[i]){ i++; } if (i == len){ count++; } if (i == 0){ //i == 0时,没有next[i-1],单独处理 pos++; } else{ pos += (i - next[i - 1]); //利用next数组进行更新 i = next[i - 1]; } } return count; } int main(){ int cas; scanf("%d", &cas); getchar(); for (int i = 0; i < cas; i++){ scanf("%s", gWord); scanf("%s", gText); int len = strlen(gWord); GenerateNext(gWord, gNext, len); int count = Kmp(gText, gWord, gNext, len); printf("%d ", count); } return 0; }