2019-02-07 14:57:05 weixin_43206161 阅读数 172
  • 图解Java数据结构和算法

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

    3197 人正在学习 去看看 佟刚

数据结构KMP实现

代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
 
void cal_next( char * str, int * next, int len )
//next数组作用返回失配位之前的最长公共前后缀!; len为返回当前的最长公共前后缀长度
{
    int i, j;
    next[0] = -1;
    for( i = 1; i < len; i++ )
    {
        j = next[ i - 1 ];
        while( str[ j + 1 ] != str[ i ] && ( j >= 0 ) )
        {
            j = next[ j ];
        }
        if( str[ i ] == str[ j + 1 ] )
        {
            next[ i ] = j + 1;
        }
        else
        {
            next[ i ] = -1;
        }
    }
}
 
int KMP( char * str, int slen, char * ptr, int plen, int * next )
{
    int s_i = 0, p_i = 0;
 
    while( s_i < slen && p_i < plen )
    {
        if( str[ s_i ] == ptr[ p_i ] )
        {
            s_i++;
            p_i++;
        }
        else
        {
            if( p_i == 0 )
            {
                s_i++;
            }
            else
            {
                p_i = next[ p_i - 1 ] + 1;
            }
        }
    }
    return ( p_i == plen ) ? ( s_i - plen ) : -1;
}
 
int main()
{
    char str[ N ] = {0};
    char ptr[ N ] = {0};
    int slen, plen;
    int next[ N ];
 
    while( scanf( "%s%s", str, ptr ) )
    {
        slen = strlen( str );
        plen = strlen( ptr );
        cal_next( ptr, next, plen );
        printf( "%d\n", KMP( str, slen, ptr, plen, next ) );
    }
    return 0;
}

运行结果如下:
在这里插入图片描述
https://blog.csdn.net/weixin_43206161

2018-09-26 22:51:33 Li_Hongcheng 阅读数 104
  • 图解Java数据结构和算法

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

    3197 人正在学习 去看看 佟刚

数据结构-KMP
重点就是对模式串next数组的理解:
比如已经知道ababab,q=4时,next[4]=2(k=2,表示该字符串的前5个字母组成的子串ababa存在相同的最长前缀和最长后缀的长度是3,所以k=2,next[4]=2。
重点是程序根据目前的结果怎么算next[5]的,
那么对于字符串ababab,我们计算next[5]的时候,此时q=5, k=2(上一步循环结束后的结果)。那么我们需要比较的是s[k+1]和s[q]是否相等,其实就是str[1]和str[5]是否相等!
为啥从k+1比较呢,因为上一次循环中,我们已经保证了str[k]和str[q](注意这个q是上次循环的q)是相等的(这句话自己想想,很容易理解),所以到本次循环,我们直接比较str[k+1]和str[q]是否相等(这个q是本次循环的q)。
如果相等,那么跳出while(),进入if(),k=k+1,接着next[q]=k。即对于ababab,我们会得出next[5]=3。 这是程序自己算的,和我们观察的是一样的。
如果不等,我们可以用”ababac“描述这种情况。
不等,进行k=next[k],这句话是说,在s[k + 1] != s[q]的情况下,我们往前找一个k,使s[k + 1]==s[q],一旦s[k + 1] != s[q],即在后缀里面找不到时,我是可以直接跳过中间一段,跑到前缀里面找,next[k]就是相同的最长前缀和最长后缀的长度。所以,k=next[k]就变成,k=next[2],即k=0。此时再比较s[0+1]和s[5]是否相等。
关于KMP里面的算法,看书直接理解。


附上自己代码

#include<bits/stdc++.h>
using namespace std;
int next[1000];
void GetNext(string a)
{
    memset(next,0,sizeof(next));
    int j,k;
    j=0;
    k=-1;
    next[0]=-1;
    while(j<a.length()-1)
    {
        if(k==-1)
        {
            next[j+1]=0;
            j++;
            k=0;
        }
        else if(a[k]==a[j])
        {
            next[j+1]=k+1;
            j++;
            k++;
        }
        else
        {
            k=next[k];
        }
    }
}
int KMP(string a,string b)
{
    GetNext(b);
    int i=0,j=0,t=0;
    while(i<a.length()&&j<(int)b.length())
    {
        if(j==-1||a[i]==b[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];
        }
    }
    if(j>=b.length())
        return(i-b.length());
    else
        return -1;
}
int main()
{
    string a="acabaabaabcacx";
    string b="abaabcac";
    cout<<KMP(a,b)<<endl;
    return 0;
}
2017-12-18 23:02:44 qq_38140099 阅读数 214
  • 图解Java数据结构和算法

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

    3197 人正在学习 去看看 佟刚

1.模板:

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int next[1010];
char s[1000],p[1000];
void GetNextval()
{
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        //p[k]表示前缀,p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
            ++j;
            ++k;
            //较之前next数组求法,改动在下面4行
            if (p[j] != p[k])
                next[j] = k;   //之前只有这一行
            else
                //因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
                next[j] = next[k];
        }
        else
        {
            k = next[k];
        }
    }
}
int KmpSearch()
{
    int i = 0;
    int j = 0;
    int sLen = strlen(s);
    int pLen = strlen(p);
    while (i < sLen && j < pLen)
    {
        //①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++
        if (j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            //②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]
            //next[j]即为j所对应的next值
            j = next[j];
        }
    }
    if (j == pLen)
        return i - j;
    else
        return -1;
}
int main()
{
    cout<<"输入文本串s:"<<endl;
    gets(s);
    cout<<"输入模式串p:"<<endl;
    gets(p);
    GetNextval();
    cout<<"模式串第一次出现的位置:"<<endl;
    cout<<KmpSearch();
    return 0;
}

2.单就next数组来说:

#include<iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int next[1000010];
char p[1000010];
int pLen;
void GetNext()
{
     pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen )//这里原本是j<pLen-1
    {
        //p[k]表示前缀,p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
            ++k;
            ++j;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}

int main()
{
    while(~scanf("%s",p)&&strcmp(p,".")!=0)
    {
        GetNext();
        for(int i=1;i<=strlen(p);i++)
            cout<<next[i];
    }

    return 0;
}
/*
ababab//输入
001234//输出
abcabcabc//输入
000123456//输出
ababcababababcabab//输入
001201234343456789//输出
*/
2016-08-05 20:13:18 Gentle_Guan 阅读数 443
  • 图解Java数据结构和算法

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

    3197 人正在学习 去看看 佟刚

数据结构实验之串一:KMP简单应用

Time Limit: 1000MS Memory limit: 65536K

题目描述

给定两个字符串string1和string2,判断string2是否为string1的子串。

输入

 输入包含多组数据,每组测试数据包含两行,第一行代表string1(长度小于1000000),第二行代表string2(长度小于1000000),string1和string2中保证不出现空格。

输出

 对于每组输入数据,若string2是string1的子串,则输出string2在string1中的位置,若不是,输出-1。

示例输入

abc
a
123456
45
abc
ddd

示例输出

1
4
-1

///ACcode

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn=10000010;
typedef struct
{
    char *top,*base;
    int Size;
    int len;
} String;

void Creat(String &s)  ///建串
{
    s.base=new char[maxn];
    s.top=s.base;
    s.Size=maxn;
    s.len=0;
}

void push(String &s,char c) ///入串...函数名有点眼熟...
{
    s.top++;
    *s.top=c;
    s.len++;
}

void add(String &s,char st[]) ///为了使 两个串 下标从零开始
{
    int i;
    for (i=0; st[i]; i++)
    {
        push(s,st[i]);
    }
}

void getnext(String &s,int next[]) /// 相当于KMP函数 其实就是和本身比较来寻找next[]数组;建议先看下面的KMP函数
{
    int i=1,j=0; ///j从 1 开始的话 next[2]=2;显然不符合next[]数组....
    next[1]=0;
    while(i<=s.len)
    {
        if (j==0||s.base[i] == s.base[j])
        {
            i++;
            j++;
            next[i]=j; /// 动态演示中很明显看出 前 j 个字符已经匹配
        }

        else
        {
            j=next[j]; /// 失配时 j“跳”到next[j]位置(也就是说next[j]之前的位置已经匹配)
        }
    }
}

void kmp(String &st,String &pt,int next[])  ///kmp ,st主串 pt模式串
{
    int i=1,j=1;
    while(i<=st.len && j<=pt.len)
    {
        if(j==0||st.base[i] == pt.base[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j]; /// 失配时 j“跳”到next[j]位置(也就是说next[j]之前的位置已经匹配)
        }
    }
    if (j>pt.len) ///说明模式串pt匹配完成
    {
        cout<<i-pt.len<<endl;
    }
    else  ///串st遍历先完了,则pt不是st子串
    {
        cout<<"-1"<<endl;
    }
}

void  print(String &s) ///打印
{
    int i;
    for (i=1; i<=s.len; i++)
    {
        cout<<s.base[i];
    }
    cout<<endl;
}

int main()
{
    int next[maxn];
    char st[maxn],pt[maxn]; ///先数组存 主串 , 模式串
    while(cin>>st>>pt)
    {
        String s,p;  ///主串 , 模式串

        Creat(s);
        Creat(p);

        add(s,st);
        add(p,pt);

        getnext(p,next);
        kmp(s,p,next);
    }
    return 0;
}


如下图

 ↓  ↓ ↓ ↓当求next[4]时,前面绿色表示已经匹配,即a匹配   next[i]就等于j 也就是next[i-1]+1


 ↓  ↓ ↓ ↓同理 ,next[6]前面有 两个绿色表示已经匹配 next[i]=j (next[i-1]+1)

next[i]失配 模式串(下面那个串)j=next[j],继续寻找匹配的位置......



 ↓  ↓ ↓ ↓同理 next[8]也如此求  next[]等于1 表示紧挨着前面没有匹配成功的  2 表示1个  以此类推..



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算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3197 人正在学习 去看看 佟刚

一,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;	
	}
} 


                           

                                  

                                 



。。。

博文 来自: u010900754
没有更多推荐了,返回首页