2019-09-20 12:48:42 shiliang97 阅读数 46
  • 图解Java数据结构算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3201 人正在学习 去看看 佟刚

kmp算法笔记

KMP算法数据结构课上讲了两天,还是晕晕乎乎的,先把《算法笔记》里的笔记放上来吧~以后想起来再看

 

笔记文件过大,出不来可以先等等

笔记很占服务器带宽,访问速度应该挺慢的~

2017-03-14 17:41:47 huangchijun11 阅读数 512
  • 图解Java数据结构算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3201 人正在学习 去看看 佟刚

一,KMP算法

       KMP算法,全称就是克努特-莫里斯-普拉特算法,是为了避免大量的重复遍历的情况。举个例子:

                                   

                                                                                                        图 1 遍历对比匹配图1

                                    

                                                                                                        图2 遍历对比匹配图2

          从图1和图2中可以看出来,在图1中如果依次匹配,到5的时候匹配不成功,此时要回头重新匹配,从i=2,j=1的位置开始匹配,这就是回溯法的思想,就这样依次来回地回溯对比验证,最后才给出一个结论是否匹配成功。

                                   

                                                                                                               图 3  思路启发一

       思路启发一,在图3中可以看到在上面的匹配中,当i=j=5的时候,是S[5]与T[5]不相等,即不匹配,此时要重新进行匹配,分析可知S[1]=T[1],S[2]=T[2],S[3]=T[3],S[4]=T[4],而T[1]不等于T[2],T[1]不等于T[3],T[1]不等于T[4],T[2]也不等于T[3],T[2]也不等于T[4],此时就不用将T[1]与S[1]\S[2]\S[3]\S[4]相匹配,直接让T[1]与S[5]进行匹配,即如图3下面的演示那样。这个时候提高了效率。

                                   

                                                                                                     图4  思路启发二

         这个思路启发二看上去肯定不符合启发一的情况,此时T[1]与S[2]是相等的,T[1]=T[2],这个时候可以直接认为T[1]=S[2],匹配下一个,即匹配T[2]与S[3],依次匹配下去就会出现匹配成功的结果。

                                  

                                                                                                        图 5   思路启发三   

        在图5中可以看到,T[1]=T[2]=S[4]=S[5],此时可以直接从T[3]开始匹配,这样就提高了效率。

                                   

                                                                                                      图6  思路启发四

          在图6思路启发四中可以看到,根据前面的一二三的经验这个时候可以很明显从T[4]开始匹配。这样得出的一些规律就是KMP算法。问题是由模式串决定的,而不是目标串决定的。主要是为了保证 i 不再回溯。避免了效率低下的问题。

二,KMP算法的实现

       1,首先get_next函数的编写

                   

#include <stdio.h>

typedef char* String;

void get_next(String T,int *next)
{
	int i = 1;
	int j = 0;
	next[1] = 0;
	
	while(i < T[0])
	{
	    if(0 == j || T[i] == T[j])
		{
		     i++;
			 j++;
			 next[i] = j;	
		}	
		else
		{
		     j = next[j];	
		}
	}
}

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main() 
{
	char str[255] = "ababaaaba";
	int next[255];
	int i = 1;
	
	str[0] = 9;
	
	get_next(str, next);
	for(i=1;i<10;i++)
	{
	     printf("%d ",next[i]);	
	}
	return 0;
}

            结果为

                                     

                                                                           获取next数组的结果图

2,KMP算法的实现

               

//返回子串T在主串S第pos个字符之后的位置 
int Index_KMP(String S,String T,int pos)
{
    int i = pos;
	int j = 1;
	int next[255];
	
	get_next(T,next);
	
	while(i<=S[0]&&J<=T[0])
	{
	     	if(S[i] == T[j])
	     	{
			    i++;
				j++;
				if(T[i]!=T[j])
				{
				     next[i] = j;	
				}		
				else
				{
				     next[i] = next[j];	
				}
			}
			else
			{
			    j = next[j];	
			}
	}
	if(j>T[0])
	{
	    return i - T[0];	
	}	
	else
	{
	   return 0;	
	}
} 


                           

                                  

                                 


2019-07-01 15:56:00 id5555 阅读数 27
  • 图解Java数据结构算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3201 人正在学习 去看看 佟刚

Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。
下面先直接给出KMP的算法流程:

  • 假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置
  • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
  • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j - next [j] 位。
  • 换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值(next 数组的求解会在下文的3.3.3节中详细阐述),即移动的实际位数为:j - next[j],且此值大于等于1。
    文章详解参考:https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

代码:

package cn.algorithm.kmp;

import java.util.Arrays;

/**
 * @Author smallmartial
 * @Date 2019/7/1
 * @Email smallmarital@qq.com
 */
public class KMPAlgorithm {

    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
       // String str2 = "BBC";

        int[] next = kmpNext("ABCDABD");
        System.out.println(Arrays.toString(next));

        int index = kmpSearch(str1,str2,next);
        System.out.println("index = "+ index);
    }

    //写出kmp搜索算法

    /**
     *
     * @param str1 源字符串
     * @param str2 子串
     * @param next 部分匹配表 是字串对应的部分匹配表
     * @return 如果返回-1 则没有匹配到
     */
    public static int kmpSearch(String str1, String str2,int[] next){
        //遍历str1
        for (int i = 0,j=0; i <str1.length() ; i++) {

            //str1.charAt(i) != str2.charAt(j)
            //kmp核心算法
            while (j > 0 && str1.charAt(i) != str2.charAt(j)){
                j = next[j -1];
            }

            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()){
                return i - j + 1;
            }
        }
        return -1;
    }

    //获取一个字符串的部分匹配值
    public static int[] kmpNext(String dest){
        //创建一个next数组保存部分匹配值
        int[] next = new int[dest.length()];

        next[0] = 0;//如果字符串长度为1 部分匹配值就是0

        for (int i = 1 ,j = 0; i < dest.length(); i++) {
            //当dest.charAt(i) != dest.charAt(j) 满足时,我们需要从next[j-1]获取新的j
            //直到我们发现有dest.charAt(i) == dest.charAt(j)成立才退出
            while (j>0 && dest.charAt(i) != dest.charAt(j)){
                j =next[j-1];
            }

            //当dest.charAt(i) == dest.charAt(j) 满足时,部分匹配值就是+1
            if (dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }

}

2016-09-11 20:11:41 biqigu 阅读数 487
  • 图解Java数据结构算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3201 人正在学习 去看看 佟刚

KMP算法解析



void GetNext(char subStr[], int  next[])
{
	int i = -1;
	int n = 0;
	int count;

	count = strlen(subStr);   
	next[0] = -1;                

	while (n<count)
	{
		if (i==-1 || subStr[n] == subStr[i])       
		{
			n++;
			i++;
			if (subStr[n] == subStr[i])                                
				next[n] =next[i];       
			else                                                  
				next[n] = i;
		}
		else                    
			i = next[i];
	}
}


int IndexKMP(char objectStr[], char subStr[],int  next[], int pos)
{
	int i, n;
	int objLength, subLength;

	objLength = strlen(objectStr);
	subLength = strlen(subStr);

	for (n = pos, i = 0;n < objLength && i < subLength;)
	{
		if (i<0 || objectStr[n] == subStr[i])
		{
			i++; n++;
		}
		else
		{
			i = next[i];
		}
	}
	if (i == subLength) return n - subLength;
	else return -1;
}


#include <iostream>
#define Length 50


void GetNext(char subStr[], int * next);
int IndexKMP(char objectStr[], char subStr[], int  next[], int pos);

int main()
{
	char objectStr[Length];
	char subStr[Length];
	int next[Length];

	scanf_s("%s", objectStr, Length);
	scanf_s("%s", subStr, Length);

	GetNext(subStr, next);

	printf_s("%d\n", IndexKMP(objectStr, subStr, next, 5));
}


      



代码下载


2017-05-18 15:24:56 qq_16184125 阅读数 250
  • 图解Java数据结构算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3201 人正在学习 去看看 佟刚

kmp.h

文件的建立

typedef int Status;
#define MAXSTRLEN 255
typedef struct 
{
char data[MAXSTRLEN+1];
int length;
}HString;


Status Concat(HString &T,HString S1,HString S2);
void StrAssign(HString &S,char cstr[]);
Status StrCopy(HString &T,HString S);
Status StrEmpty(HString S);
Status StrCompare(HString S,HString T);
Status StrLength(HString S);
Status ClearString(HString &S);
Status Concat(HString &S);
Status SubString(HString &Sub,HString S,int pos,int len);
int Index(HString S,HString T);
Status Replace(HString &S,HString T,HString V);
Status StrInsert(HString &S,int pos,HString T);
Status StrDelete(HString &S,int pos,int len);
Status DestroyString(HString &S);
Status Index_KMP(HString S,HString T);
void get_nextval(HString T,int nextval[]);
void DispStr(HString s);
void get_next(HString T,int next[]);
Status Index_KMP1(HString S,HString T);


KMPS.cpp 文件的建立



#include "stdafx.h"
#include "kmp.h"




Status Concat(HString &T,HString S1,HString S2)
{
int i,uncut;
if(S1.length+S2.length<=MAXSTRLEN)
{
T.length=S1.length+S2.length;
for(i=1;i<=S1.length;i++)
           T.data[i]=S1.data[i];
for(i=S1.length+1;i<=S1.length+S2.length;i++)
T.data[i]=S2.data[i-S1.length];
uncut=TRUE;
}
else if(S1.length<MAXSTRLEN)
{
for(i=1;i<=S1.length;i++)
T.data[i]=S1.data[i];
        for(i=S1.length+1;i<=MAXSTRLEN;i++)
T.data[i]=S2.data[i-S1.length];
T.length=MAXSTRLEN;
uncut=FALSE;
}
else
{
        for(i=1;i<=MAXSTRLEN;i++)
T.data[i]=S1.data[i];
uncut=FALSE;
}


return uncut;
}


void StrAssign(HString &S,char cstr[])
{

int i;
for (i=1;cstr[i-1]!='\0';i++)
S.data[i]=cstr[i-1];
S.length=i-1;
}


Status StrCopy(HString &T,HString S)
{
int i=0;
T.length=S.length;
while(S.data[i]!='\0')
{
T.data[i]=S.data[i];
}
return OK;
}


Status StrEmpty(HString S)
{
if(S.length==0&&S.data[1]=='\0')
return TRUE;
else
return FALSE;
}


Status StrCompare(HString S,HString T)
{
    
return OK;
}


Status StrLength(HString S)
{

return S.length;
}


Status ClearString(HString &S)
{
int i;
for(i=1;i<=S.length;i++)
S.data[i]='\0';
S.length=0;
return OK;
}


Status Concat(HString T,HString S1,HString S2)
{
int i;
T.length=S1.length+S2.length;
for(i=1;i<=S1.length;i++)
           T.data[i]=S1.data[i];
for(i=S1.length+1;i<=S1.length+S2.length;i++)
T.data[i]=S2.data[i-S1.length];
return OK;
}


Status SubString(HString &Sub,HString S,int pos,int len)
{
int i;
for(i=pos;i<=len;i++)
Sub.data[i-pos-1]=S.data[i];
Sub.data[0]=len;
return OK;
}


int Index(HString S,HString T)
{
int i=1,j=0;
while (i<=S.length && j<T.length) 
{ if (S.data[i]==T.data[j])
{ i++;
j++;
}
else
{ i=i-j+1;
j=0;
}
}
if (j>=T.length)
return(i-T.length-1);
else
return(-1);
}


Status Replace(HString &S,HString T,HString V)
{
    
return OK;
}


Status StrInsert(HString &S,int pos,HString T)
{
int i;
    HString P;
P.length=S.length+T.length;
for(i=1;i<=pos-1;i++)
        P.data[i]=S.data[i];
for(i=pos;i<=T.length;i++)
P.data[i]=T.data[i-pos+1];
for(i=pos;i<=S.length;i++)
P.data[i+T.length]=S.data[i];
for(i=1;i<=P.length;i++)
S.data[i]=P.data[i];
S.length=P.length;
return OK;
}


Status StrDelete(HString &S,int pos,int len)
{


HString P;
int i;
    P.length=S.length-len;
for(i=1;i<=pos-1;i++)
        P.data[i]=S.data[i];
    for(i=pos+len;i<=S.length;i++)
P.data[i-len]=S.data[i];
return OK;
}


Status DestroyString(HString &S)
{


free(S.data);
return OK;
}


Status Index_KMP(HString S,HString T)
{
   int nextval[MAXSTRLEN+1];
   get_nextval(T,nextval);
   int i,j;
   j=1;
   i=1;
   while(i<=S.length&&j<=T.length)
   {
  if(j==0||S.data[i]==T.data[j])
  {
  ++i;
  ++j;
  }
  else 
  {
  
  j=nextval[j];
  }
   }
   if(j>T.length)
  return i-T.length;
   else 
  return 0;
}


void get_nextval(HString T,int nextval[])
{
int i,j;
i=1;
nextval[1]=0;
j=0;
while(i<T.length)
{
if(j==0||T.data[i]==T.data[j])
{
++i;
++j;
if(T.data[i]!=T.data[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else 
j=nextval[j];
}
}
void DispStr(HString s)
{ int i;
if (s.length>0)
{ for (i=1;i<=s.length;i++)
printf("%c",s.data[i]);
printf("\n");
}
}


void get_next(HString T,int next[])
{
   int i,j;
i=1;
   next[1]=0;
   j=0;
   while(i<T.length)
   {
  if(j==0||T.data[i]==T.data[j])
  {
  ++i;
  ++j;
  next[i]=j;
  
  }
  else
  j=next[j];
   }
}


Status Index_KMP1(HString S,HString T)
{
   int next[MAXSTRLEN+1];
   get_next(T,next);
   int i,j;
   j=1;
   i=1;
   while(i<=S.length&&j<=T.length)
   {
  if(j==0||S.data[i]==T.data[j])
  {
  ++i;
  ++j;
  }
  else 
  {
  
  j=next[j];
  }
   }
   if(j>T.length)
  return i-T.length;
   else 
  return 0;
}

主函数所在的文件

#include "stdafx.h"
#include "kmp.h"


int main(int argc, char* argv[])
{
//printf("Hello World!\n");
int j,a;
int nextval[MAXSTRLEN+1],next[MAXSTRLEN+1];
HString s,t;
StrAssign(s,"abcabcdabcdeabcdefabcdefg");
StrAssign(t,"abcdeabcdefab");
printf("串s:");DispStr(s);
printf("串t:");DispStr(t);


get_nextval(t,nextval); //由模式串t求出nextval值
get_next(t,next);
printf("    j   ");
for (j=1;j<=t.length;j++)
printf("%4d",j);
printf("\n");
printf(" t[j]   ");
for (j=1;j<=t.length;j++)
printf("%4c",t.data[j]);
printf("\n");


printf("\n");
printf(" nextval");
for (j=1;j<=t.length;j++)
printf("%4d",nextval[j]);
printf("\n");
printf("改进的KMP算法:\n");
a=Index_KMP(s,t);
printf("  t在s中的位置=%d\n",a);
printf("<------------------------------------------------------------>\n");
printf("    j   ");
for (j=1;j<=t.length;j++)
printf("%4d",j);
printf("\n");
printf(" t[j]   ");
for (j=1;j<=t.length;j++)
printf("%4c",t.data[j]);
printf("\n");
printf(" next   ");
for (j=1;j<=t.length;j++)
printf("%4d",next[j]);
printf("\n");


printf("旧版的KMP算法:\n");
a=Index_KMP1(s,t);
printf("  t在s中的位置=%d\n",a);
    system("pause");
return 0;
}

KMP算法

阅读数 42

没有更多推荐了,返回首页