作者：小成Charles
商业工作，学习交流请添加Vx：Lcc-Triumph
原创作品
转载请标注原创文章地址：https://blog.csdn.net/weixin_42999453/article/details/115711676

Github代码下载地址：https://github.com/xiaocheng99/c_project

引言

这是一个学习C语言的笔记开篇，做一些简单有趣的c小程序。下面是C语言字符串关键字的匹配算法讲解笔记

一、主函数

这段代码块定义了一个全局变量pattern作为目标关键词，其中'\0'是字符串的结束标志。charline是从getline获取到的被匹配句子，while循环条件会一直进行字符串的输入，直到出现一个完整的句子就会执行strIndex函数来判断当前句子是否包含关键字，下面来讲解函数getLine和函数strIndex

#include <stdio.h>
#define MAXLINE 1000

char pattern[] = "charles\0";
int main()
{
	char charLine[MAXLINE];
	int found = 0;
	while (getLine(charLine, MAXLINE)>0)
	{
		//printf("keypress:%s", charLine);
		if (strIndex(charLine,pattern)>=0)
		{
			printf("\"loud\" postion:%s", charLine);
			found++;
		}
	}

	return found;
}

二、getLine函数

这里其实是进行字符串的输入，当输入为换行时，缓冲区会判断到为换行符'\n'，这时候我们就判定为当前为一个句子，跳出循环，返回一个i,此时的i是大于零的，在主函数里面就是一个真值，如果当前为EOF(End Of File)，即为结束（windows下按Ctrl+Z再回车），此时不返回值，在主函数里面就是假，不执行接下来的程序。

int getLine(char line[],int max)
{
	int c, i;
	i = 0;
	while (--max > 0 && (c=getchar())!=EOF && c!= '\n')
	{
	line[i++] = c;
	}
	if (c=='\n')
	{
		line[i++] = c;
		line[i] = '\0';
		return i;

	}
}

三、strIndex函数

这里是实现字符串匹配的主要算法逻辑，第一个for循环首先对字符串进行遍历，并且第二个for循环一直在对字符串与关键词的第一个字符进行比较，如果发现字符串的某一个字符和关键词的第一个字符相等，那么第二个for循环就会执行，去依次判断字符串后面几个和关键词的字符是否相同，由于关键词有一个‘\0’结束符，当完全匹配的时候,关键词字符串数组下标将会累加到结束符的下标，所以当关键词下标指向的字符为'\0'时，则找到所匹配的字符串，并且返回一个大于零的下标。主函数收到后，打印当前句子。

int strIndex(char source[],char serachfor[])
{
	int i, j, k;
	for (i = 0; source[i] != '\0'; i++)
	{
		for (j = i, k = 0; serachfor[k] != '\0'&&source[j] == serachfor[k];j++,k++);
		if (k>0&&serachfor[k]=='\0')
		{
			return i;
		}
	}
	return -1;
}

Github代码下载地址：https://github.com/xiaocheng99/c_project

作者：小成Charles
商业工作，学习交流请添加Vx：Lcc-Triumph
原创作品
转载请标注原创文章地址：https://blog.csdn.net/weixin_42999453/article/details/115711676

给定一定数量的关键字，对任一篇文本，寻找文本中包含哪些关键字

例如关键字集合如下：

而待检测的文本如下：

当前算法的目的就是从test.txt中快速的检索有没有给定的keyWord.txt中的关键字

具体的代码下载地址是：http://download.csdn.net/detail/sinat_22013331/9551006，这部分代码是用C＃写的，如果要java或者其他语言的版本，可以对照着改动一些。

这个文本处理需要一个算法， 普通的文本处理直接去遍历所有的关键字，但是这种算法太复杂，时间复杂度太高。

之前的文章中有说过，实际用到的算法，为了加快执行速度，都是在时间和空间上做的兑换,用存储空间的增加来换取执行时间的减小。

这里同样可以，通过增加存储空间来减少程序执行时间。

可以选择开一个数组，数组的长度是char类型的最大长度加一。

数组的相应字符对应位置上的数值用二进制表示。假设关键字的长度最长为15，则可以用两个字节的数字来表示，也就是一个short类型。

假设数字为 0000 0000 0010 0110， 也就是38。则表示当前这个字符，可能出现在关键字的第2,3,6位上。由此做倒排索引，可以更方便的得到答案。

//对应位上的值存放的是每个字符在对应位数上是否存在敏感词，
//比如fastPositionCheck[7] = 38, 也就是0010 0110  表示某个ascll码为7的字符可能出现在关键字的第2，3，6位上
private short[] fastPositionCheck = new short[char.MaxValue + 1];

这个实现方案可以变成：首先创建一个关键字字典，在这个字典中包含所有的关键字。同时在这个字典中提供针对某个字符的快速检验方法，比如说查看当前关键字是否出现在第一位。

创建的字典如下：

//存放所有关键词
private HashSet<string>[] words = new HashSet<string>[ char.MaxValue + 1 ];

字典中的快速检验方法，这里提供两种，分别是验证某字符是否会出现在关键字的第几位上，以及当前字符时候是某关键字的第一位，如下：

        //对应位上的值存放的是每个字符在对应位数上是否存在敏感词，
        //比如fastPositionCheck[7] = 35, 也就是0010 0011  表示某个ascll码为7的字符可能出现在关键字的第1，2，6位上
        private short[] fastPositionCheck = new short[char.MaxValue + 1];
        
        //存放以某个字符为第一位的关键词的长度
        private short[] fastLengthCheck = new short[char.MaxValue + 1];

于是字典建立完成之后，就要将所有的关键字添加到字典中，在添加的时候，对各种存储空间赋值。操作如下：

        /// <summary>
        /// 向字典中添加关键词
        /// </summary>
        /// <param name="word"></param>
        /// <returns></returns>
        public bool AddWord( string word )
        {
            bool result = false;
            try
            {
                maxStoreWordLength = Math.Max(maxStoreWordLength, word.Length);
                minStoreWordLength = Math.Min(minStoreWordLength, word.Length);

                //这些运算符的运用简直了，神来之笔
                for (int i = 0; i < word.Length; i++)
                {
                    fastPositionCheck[word[i]] |= (short)(1 << i);
                }

                //记录以某个字开头的关键字的长度信息，左移位数长度为该字符串长度减一
                fastLengthCheck[word[0]] |= (short)(1 << (word.Length - 1));

                if (words[word[0]] == null)
                {
                    words[word[0]] = new HashSet<string>();
                }

                if (!words[word[0]].Contains(word))
                {
                    words[word[0]].Add(word);
                }
                result = true;

            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }

            return result;
        }
    }

到这里，一个完整的字典就建立完成了，下面来说字典的使用。

在字典的使用中，前面已经讲过KMP算法了，这里的思路有点像，还是从string的第一个字符开始，逐渐向后遍历，直到最后一个字符。遍历的时候作快速判定，此时的判定依据就是前面提到的几个数组。具体代码如下：

        public void CheckNormalWord(string text )
        {
            
            int index = 0;
            while (index < text.Length)
            {

                //首先判断当前字符是否是某关键字的第一个字符，不是时就继续向下遍历
                if ((keywordDict.FastCheck[text[index]] & 1) == 0)
                {
                    do
                    {
                        index++;
                    }
                    while ( (index < text.Length) && ((keywordDict.FastCheck[text[index]] & 1) == 0) );

                    if (index >= text.Length)
                    {
                        break;
                    }
                }

                //此时已经判定，当前的这个字符会出现在关键词的第一位上
                //在判断
                char begin = text[index];
                int jump = 1;
                for (int j = 0; j <= Math.Min(keywordDict.MaxWordLength, text.Length - index - 1); j++)
                {
                    char current = text[index + j];
                    
                    //判断当前字符是否会出现在关键字的对应位上，实现快速判断
                    if ((keywordDict.FastCheck[current] & (1 << Math.Min(j, keywordDict.MaxWordLength))) == 0)
                    {
                        break;
                    }
                    
                    //当判决的长度大于关键字的最小长度时，当前的截取字符串有可能会是关键字，要做详细判定
                    if (j + 1 >= keywordDict.MinWordLength)
                    {
                        if ((keywordDict.FastLength[begin] & (1 << Math.Min(j, keywordDict.MaxWordLength))) > 0)
                        {
                            string sub = text.Substring(index, j + 1);

                            //在字典中搜索判断，得出结论。同时给出跳转位数，供下一次跳转用
                            if (keywordDict.Words[begin] != null && keywordDict.Words[begin].ContainsKey(sub))
                            {
                                jump = sub.Length;
                                Console.WriteLine(sub);
                            }
                        }
                    }
                }

                index += jump;
            }
        }

这样就实现了整个文本中搜索指定关键字的算法。具体的代码详见 https://github.com/BLYang7/HighlightKeyword