文本文件单词的检索与计数（解法二：C++代码实现）

布满荆棘的人生 2023-10-04 08:08 2阅读 0赞

### 文章目录 ###

*   *  一、实验任务
     *  二、实验要求
     *  三、在文本中查找的算法
     *   *  1.简单模式匹配算法
         *  2.KMP算法
     *  四、 文本文档内容展示
     *  五、运行截图展示
     *  六、附录
     *   *  1.解法一（java篇）个人CSDN链接
         *  2.参考文献

## 一、实验任务 ##

*  建立一个文本文件，统计给定单词在文本文件中出现的总次数及位置。

## 二、实验要求 ##

*  文本文件中每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写，统计给定单词在文本文件中出现的总次数，检索输出的某个单词出现在文本中的行号、在该行中出现的位置。
 *  设计数据量大的文本，进行子串的查询处理，分析算法运行的时间效率，对所有输出的匹配位置结果进行验证，以证明算法设计和实现的正确性。
 *  用朴素模式匹配算法或KMP算法实现字符串定位；可正确读取，保存文本。

## 三、在文本中查找的算法 ##

### 1.简单模式匹配算法 ###

#include<iostream>
    using namespace std;
    //返回子串t在主串t中第pos个字符之后的位置；若不存在，函数返回0
    //t非空，1≤pos≤s.size()
    int Index(string s, string t, int pos=0)        //默认为0，默认从第一个元素开始查找
    {
    	int i = pos;				//主串t当前下表
    	int j = 0;				//子串t当前下表
    	while (i<s.size() && j<t.size())	//i小于s长度，j小于t长度，循环继续
    	{
    		if (s[i] == t[j])
    		{
    			i++;
    			j++;
    		}
    		else				//指针退回，重新开始匹配
    		{
    			i = i - j + 1;	        //i退回到上一次匹配首位的下一位
    			j = 0;			//j退回到子串t的首位
    		}
    	}
    	if (j >= t.size())
    		return i - t.size() + 1;	//i - t.size()表示从s[4]开始重复，+1表示该元素为第5个元素
    	else
    		return 0;
    }
     
    int main()
    {
    	string s = "helloworld";
    	string t = "hello";
    	cout << Index(s, t)<<endl;
    	return 0;
    }

### 2.KMP算法 ###

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<string.h>
    #include<Windows.h>
    #include <iostream>
    using namespace std;
    #define BUF_SIZE 500
    int counts = 0;
    int direction[200] = {0};
    typedef struct seqstring {
    	char string[100];
    	int length;
    }seqstring;
    
    void getnext(seqstring p, int next[]) {
    	int i, j;
    	i = 0;//指向字符串每个字符的下标
    	j = -1;
    	next[i] = j;//next[0]放上-1 
    	while (i < p.length) {//没有到达结尾的话 
    		if (j == -1 || p.string[i] == p.string[j]) {//如果是第一个字符或遇到相同的字符
    			next[++i] = ++j;
    		}
    		else {
    			j = next[j];
    		}
    	}
    	for (i = 0; i < p.length; i++) {//输出next[]值 
    		//printf("%d ", next[i]);
    	}
    }
    
    int kmp(seqstring t, seqstring p, int next[]) {
    	int i, j;
    	i = j = 0;
    	while (true) {
    		if (j == -1 || t.string[i] == p.string[j]) {
    			i++; j++;
    		}
    		else {
    			j = next[j];
    		}
    
    		if (!(i < t.length && j < p.length)) {
    			if (j == p.length) {
    				direction[counts] = i - p.length;
    				counts++;
    				j = 0;
    			}
    			if (i == t.length) {
    				return 0;
    			}
    		}
    
    	}
    	if (j == p.length) 
    	{ 
    		return i - p.length;
    	}
    	else
    	{
    		return -1;
    	}
    		
    }
    int  main() {
    	seqstring t, p;
    	int next[50];
    
    
    	DWORD	nIn;
    	char buffer[BUF_SIZE] = "";
    	HANDLE handle = CreateFile("E://javaText//javaOne//JavaSE//document.txt",
    		GENERIC_READ,
    		FILE_SHARE_READ,
    		NULL,
    		OPEN_EXISTING,
    		FILE_ATTRIBUTE_NORMAL,
    		NULL);
    	if (handle == INVALID_HANDLE_VALUE) {
    		printf("%d", GetLastError());
    		return -1;
    	}
    	ReadFile(handle, buffer, BUF_SIZE, &nIn, NULL);
    
    
    	strcpy(t.string, buffer);
    	printf("%s\n", t.string);
    	t.length = strlen(t.string);
    
    	printf("请输入待查内容:");
    	scanf("%s", p.string);
    	printf("%s\n", p.string);
    	p.length = strlen(p.string);
    	//printf("next:");
    	getnext(p, next);
    	kmp(t, p, next);
    	printf("\n%d\n", counts);
    	printf("该目标出现的位置为：\n");
    	for (int i = 0; i < counts; i++) {
    		cout << direction[i]<<"  ";
    	}
    }

## 四、 文本文档内容展示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70]

## 五、运行截图展示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 2]

## 六、附录 ##

### 1.解法一（java篇）个人CSDN链接 ###

[https://blog.csdn.net/m0\_48170265/article/details/114684371][https_blog.csdn.net_m0_48170265_article_details_114684371]

### 2.参考文献 ###

①朴素模式匹配算法：  
[https://blog.csdn.net/happyjacob/article/details/80850975][https_blog.csdn.net_happyjacob_article_details_80850975]  
②KMP算法：  
[https://blog.csdn.net/dark\_cy/article/details/88698736][https_blog.csdn.net_dark_cy_article_details_88698736]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210312205854132.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210312210005506.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210312210238247.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[https_blog.csdn.net_m0_48170265_article_details_114684371]: https://blog.csdn.net/m0_48170265/article/details/114684371
[https_blog.csdn.net_happyjacob_article_details_80850975]: https://blog.csdn.net/happyjacob/article/details/80850975
[https_blog.csdn.net_dark_cy_article_details_88698736]: https://blog.csdn.net/dark_cy/article/details/88698736