hdoj1203—-背包

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1203
折腾了N久,终于AC了。得到了一些新知识,还是值得的。
1。背包问题如何记录选了哪些物品?
2。背包的dp[]数组不一定用来存储将前i个物品放入体积为j的背包中的value最大和,还可以是value之积(如这题),是具体情况而定。(如果是之积,那么dp[]数组应初始化为1)
这两个小问题记在笔记本上了,就不发了。。提醒自己记得复习而已。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	while(n!=0 || m!=0)
	{
		int i,j,w[10002];
		float v[10002];
		float dp[10001];
		for(i=1;i<=m;i++)
			scanf("%d %f",&w[i],&v[i]);
		for(i=0;i<=n;i++)
			dp[i]=1;
		for(i=1;i<=m;i++)
			for(j=n;j>=0;j--)
				if(w[i]<=j)
					if(dp[j-w[i]]*(1-v[i])<=dp[j])
					{
						dp[j]=dp[j-w[i]]*(1-v[i]);
					}
	

		float result=(1-dp[n])*100;
		printf("%.1f%%\n",result);
		scanf("%d %d",&n,&m);
	}



//system("pause");
return 0;
}

hdoj2066——最短路

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2066
最短路入门题,开始用floyd,超时。改用dijkstra,对每个与草儿家相邻的城市求一次dij,WA。。检查很久不知错误何在,看了一篇解题报告,原来是自己没有理解有重边这句话的含义。重边是指两个点之间有多条边,但权值可能不同。所以map[][]要保存两点间边权最小的边。
事实上,此题用一次dijstra就行了,把草儿家看成源点,把与之相邻的点看成距离为0。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
typedef struct Dist{
	int pre;
	int dist;
}Dist;
Dist dist[1002];
int map[1002][1002];
int visit[1002];
void dij(int n)
{
	int i,j,k;
	for(i=1;i<=n;i++)
	{
		dist[i].dist=map[0][i];
		dist[i].pre=0;
		visit[i]=false;
	}
	dist[0].dist=0;
	dist[0].pre=-1;
	visit[0]=true;
	for(i=1;i<=n;i++)
	{
		int min=INT_MAX,k=-1;
		for(j=0;j<=n;j++)
			if(!visit[j] && dist[j].dist<min)
			{
				min=dist[j].dist;
				k=j;
			}
		if(k==-1) return;
		visit[k]=true;
		for(j=0;j<=n;j++)
		{
			if(!visit[j] && map[k][j]!=INT_MAX && dist[k].dist+map[k][j]<dist[j].dist)
			{
				dist[j].dist=dist[k].dist+map[k][j];
				dist[j].pre=k;
			}
		}
	}
	return;
}
int main()
{
	int t,s,d;
	while(scanf("%d %d %d",&t,&s,&d)!=EOF)
	{
		memset(visit,0,sizeof(visit));
		int i,j,k,n=-1,nei[1002],dest[1002];
		for(i=0;i<=1000;i++)
			for(j=0;j<=1000;j++)
			{
				if(i!=j)
					map[i][j]=INT_MAX;
				else
					map[i][j]=0;
			}
		while(t--)
		{
			int a,b,time;
			scanf("%d %d %d",&a,&b,&time);
			if(time<map[a][b])
			map[a][b]=map[b][a]=time;
			if(a>n) n=a;
			if(b>n) n=b;
		}
		for(i=1;i<=s;i++)
		{
			scanf("%d",&nei[i]);
			map[0][nei[i]]=0;
			map[nei[i]][0]=0;
		}
		for(i=1;i<=d;i++)
			scanf("%d",&dest[i]);
		dij(n);
		int min=INT_MAX;
		for(i=1;i<=d;i++)
		{
			if(dist[dest[i]].dist<min)
				min=dist[dest[i]].dist;
		}
		printf("%d\n",min);
	}
return 0;
}

水题的教训

一道水题,但是被它虐了。。每行后面没有空格。谨记啊,注意细节

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int t;
	scanf("%d",&t);
	char s[100][100];
	while(t--)
	{
		int n,i,j;
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				s[i][j]=' ';
		for(i=1;i<=n;i++)
		{
			s[i][i]='X';
			s[i][n+1-i]='X';
		}
		for(i=1;i<=(n+1)/2;i++)
		{
			for(j=1;j<=(n-i+1);j++)
				printf("%c",s[i][j]);
			printf("\n");
		}
		for(i=(n+1)/2+1;i<=n;i++)
		{
			for(j=1;j<=i;j++)
				printf("%c",s[i][j]);
			printf("\n");
		}
	
		printf("\n");
	}
return 0;
}

hdoj1057(模拟)

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1057
真是水题中的战斗机,纠缠哥好久~~,还有,今天校赛被虐了,4道题,人家都七八道。。哎,后来者该如何居上呢。。还是起步太晚,练得又少。加油~

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int t;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		int i,j,n,d[16];
		int map[22][22],maze[22][22];
		scanf("%d",&n);
		for(i=0;i<=15;i++)
			scanf("%d",&d[i]);
		for(i=0;i<=21;i++)
			for(j=0;j<=21;j++)
				map[i][j]=0;
		for(i=0;i<=21;i++)
			for(j=0;j<=21;j++)
				maze[i][j]=0;
		for(i=1;i<=20;i++)
			for(j=1;j<=20;j++)
				scanf("%d",&map[i][j]);
		int flag=1;
		while(n--)
		{
			flag=!flag;
			if(!flag)
				for(i=1;i<=20;i++)
					for(j=1;j<=20;j++)
					{
						int xh=map[i][j]+d[map[i][j]+map[i-1][j]+map[i+1][j]+map[i][j-1]+map[i][j+1]];
						if(xh>3)
							maze[i][j]=3;
						else if(xh<0)
							maze[i][j]=0;
						else
							maze[i][j]=xh;
					}
			else
				for(i=1;i<=20;i++)
					for(j=1;j<=20;j++)
					{
						
						int xhxh=maze[i][j]+d[maze[i][j]+maze[i-1][j]+maze[i+1][j]+maze[i][j-1]+maze[i][j+1]];
						if(xhxh>3)
							map[i][j]=3;
						else if(xhxh<0)
							map[i][j]=0;
						else
							map[i][j]=xhxh;
					}
		}
		if(flag)
			for(i=1;i<=20;i++)
			{
				for(j=1;j<=20;j++)
					if(map[i][j]>=3)
						printf("#");
					else if(map[i][j]<=0)
						printf(".");
					else if(map[i][j]==1)
						printf("!");
					else
						printf("X");
					printf("\n");
			}
		else
			for(i=1;i<=20;i++)
				{
					for(j=1;j<=20;j++)
						if(maze[i][j]>=3)
							printf("#");
						else if(maze[i][j]<=0)
							printf(".");
						else if(maze[i][j]==1)
							printf("!");
						else
							printf("X");
						printf("\n");
				}
			if(t!=0)
			printf("\n");

	}
//system("pause");
return 0;
}

无向图判环

以下内容摘自http://blog.csdn.net/memray/article/details/8021865
判断无向图中是否存在回路(环)的算法描述

如果存在回路,则必存在一个子图,是一个环路。环路中所有顶点的度>=2。

算法:

第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一。

第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶点重复步骤一。

如果最后还有未删除顶点,则存在环,否则没有环。

算法分析:

由于有m条边,n个顶点。如果m>=n,则根据图论知识可直接判断存在环路。

(证明:如果没有环路,则该图必然是k棵树 k>=1。根据树的性质,边的数目m = n-k。k>=1,所以:m

如果m

对上面的摘录做些记录:
设置顶点度数数组degree[],用邻接矩阵存储边,同时更新degree数组。后续步骤类似拓扑排序。

hdoj1059

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1059
哎,很久不练,把背包题忘得一干二净了,对着以前记的模板敲了一遍。。这题是多重背包,开始直接转为01背包,TLE。用二进制优化后AC。。(还是用了300多MS~~)

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int main()
{
	int n[7],cases=0;
	scanf("%d %d %d %d %d %d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6]);
	while(n[1]!=0 ||n[2]!=0||n[3]!=0||n[4]!=0||n[5]!=0||n[6]!=0)
	{
		int sum=0,i,j,k;
		for(i=1;i<=6;i++)
			sum+=i*n[i];
		if(sum%2==1)
		{
			printf("Collection #%d:\n",++cases);
			printf("Can't be divided.\n\n");
			scanf("%d %d %d %d %d %d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6]);
			continue;
		}
		sum/=2;
		int count=1;
		int f[60002],value[60002],size[60002];
		f[0]=0;
		for(i=1;i<=60000;i++)
			f[i]=INT_MIN;
		for(i=1;i<=6;i++)
		{
			int c=n[i];
			for(k=1;k<=c;k*=2)
			{
				value[count]=k*i;
				size[count++]=k*i;
				c-=k;
			}
			if(c>0)
			{
				value[count]=c*i;
				size[count++]=c*i;
			
			}
		}
		for(i=1;i<=count-1;i++)
			for(j=sum;j>=0;j--)
			{
				if(size[i]<=j)
				{
					if(f[j-size[i]]+value[i]>f[j])
						f[j]=f[j-size[i]]+value[i];
				}
			}
		if(f[sum]==sum)
		{
			printf("Collection #%d:\n",++cases);
			printf("Can be divided.\n\n");
		}
		else
		{
			printf("Collection #%d:\n",++cases);
			printf("Can't be divided.\n\n");
		}
	
		scanf("%d %d %d %d %d %d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6]);		
	}


	//system("pause");
	return 0;
}

并查集样例

用并查集可以对无向图判环,每读入一条边,合并该边的两个顶点所在的集合,如果合并时两个顶点已经在一个集合中(说明已经有一条路径连通这两个顶点),则说明出现了环。
用并查集可以对有向图和无向图判连通性。

//数组下标是集合元素,数组的值用来指示父节点的下标,根节点的值是它本身
#include<stdio.h>
int bin[100000];
int find(int x)
{
      int r = x;
      while (bin[r]!=r)
          r = bin[r];       
      int i = x;
      while (i!=r)//路径压缩
      {   
          int j = bin[i];
		  bin[i] = r;
          i = j;
      }
	  return r;
}
void merge(int a,int b)//a,b是不同集合的根节点,所以合并两个集合前,先要判断两个集合是否为同一个集合,然后找到各自根节点
{
    int fx=find(a);
    int fy=find(b);
    if(fx!=fy)
    bin[fy]=fx;
    return;
}
int main()
{
	int i;
	for(i=1;i<=100000;i++)//初始化
	{
		bin[i]=i;
	}
	return 0;
}

hdoj1301

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1301
这道题好悲催,本来很简单一道题,就是求最小生成树,但是几个细节没注意,WA好久~~
map数组应初始化为无穷大,而不是0.。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Dist{
    int pre;
    int dist;
}Dist;
Dist dist[30];
bool visit[30];
int map[30][30];
void prim(int n)
{
    int i,j;
    visit[1]=true;
    dist[1].dist=0;
    for(i=2;i<=n;i++)
    {
        dist[i].dist=map[1][i];
        dist[i].pre=1;
        visit[i]=false;
    }
    for(i=1;i<=n-1;i++)
    {
        int min=1000000,k=0;
        for(j=1;j<=n;j++)
        {
            if(!visit[j] && dist[j].dist<min)
            {
                min=dist[j].dist;
                k=j;
            }
        }
        if(k==0) return;
        visit[k]=true;
        for(j=1;j<=n;j++)
        {
            if(!visit[j] && map[k][j]<dist[j].dist)
            {
                dist[j].dist=map[k][j];
                dist[j].pre=k;
            }
        }
    }
    return;
}
int main()
{
    int n,i,j;
    scanf("%d",&n);
    while(n!=0)
    {
        getchar();
        memset(visit,0,sizeof(visit));
        memset(dist,0,sizeof(dist));
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				map[i][j]=10000000;
        int k,b,t;
        char v,a;
        for(i=1;i<=n-1;i++)
        {
            scanf("%c %d",&v,&t);
            getchar();
            for(j=1;j<=t;j++)
            {
                scanf("%c %d",&a,&b);
                getchar();
                map[i][a-'A'+1]=b;
				map[a-'A'+1][i]=b;
            }
			
        }
        prim(n);
        int sum=0;
        for(i=1;i<=n;i++)
            sum+=dist[i].dist;
        printf("%d\n",sum);
    
    
        scanf("%d",&n);    
    }
//system("pause");
return 0;
}

hdoj1233

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1233
裸的最小生成树。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct Dist{
	int pre;
	int dist;
}Dist;
Dist dist[102];
bool visit[102];
int map[102][102];
void prim(int n)
{
	int i,j;
	visit[1]=true;
	dist[1].dist=0;
	for(i=2;i<=n;i++)
	{
		dist[i].dist=map[1][i];
		dist[i].pre=1;
		visit[i]=false;
	}
	for(i=1;i<=n-1;i++)
	{
		int min=100000,k=0;
		for(j=1;j<=n;j++)
		{
			if(!visit[j] && dist[j].dist<min)
			{
				min=dist[j].dist;
				k=j;
			}
		}
		if(k==0) return;
		visit[k]=true;
		for(j=1;j<=n;j++)
		{
			if(!visit[j] && map[k][j]<dist[j].dist)
			{
				dist[j].dist=map[k][j];
				dist[j].pre=k;
			}
		}
	}
	return;	
}
int main()
{
	int n,i,a,b,w;
	scanf("%d",&n);
	while(n!=0)
	{
		memset(dist,0,sizeof(dist));
		memset(visit,0,sizeof(visit));
		memset(map,0,sizeof(map));
		for(i=1;i<=n*(n-1)/2;i++)
		{
			scanf("%d %d %d",&a,&b,&w);
			map[a][b]=w;
			map[b][a]=w;
		}
		prim(n);
		int  sum=0;
		for(i=1;i<=n;i++)
			sum+=dist[i].dist;
		printf("%d\n",sum);
		scanf("%d",&n);	
	}
//system("pause");
return 0;
}

hdoj1232

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1232
一道水题,但一开始还是想错了,开始的想法非常二~~。开始是这样想的:因为一棵树要连通的边数最少也就是当它是最小生成树的时候,也就是n-1.于是我用邻接矩阵存储边,数出已经有几条不同的边(count),然后答案就是n-1-count.
对于我这样的菜鸟来说,初看这个思路好像没问题,其实问题很大,因为只有当已经有的边全部是最小生成树中的边时,答案才正确(前面几组sample好像都符合–!,害我想了半天。。~);否则,如果其中有的边不是最小生成树中的,那么即使最终边数达到n-1,还是有点没有连通。换句话说,只有n-1条构成最小生成树的边才能连通所有点。(或者可以这样认为,只有这些已经有的边之间不存在环时才行)
不知道这样说对不对,可能有错误,望大牛指正^_^
最终用dfs找出所有连通分量,解决此题。(网上搜了下都说这道题是并查集的经典题,可惜我还没学。。)
<突然发现最近博客里的文章都是解题报告了。。最近没学其他技术,只能靠写解题报告撑着了。。~>

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Edge{
	int to;
	int next;
}Edge;
bool visit[1001];
Edge edge[10001];
int head[1001];
void dfs(int x)
{
	visit[x]=true;
	int k;
	for(k=head[x];k!=-1;k=edge[k].next)
	{
		if(!visit[edge[k].to])
			dfs(edge[k].to);
	}
	return;
}
int main()
{
	int n,k,m,i;
	scanf("%d",&n);
	while(n!=0)
	{
		memset(head,-1,sizeof(head));
		memset(edge,0,sizeof(edge));
		memset(visit,0,sizeof(visit));
		scanf("%d",&m);
		int a,b;
		for(k=1;k<=2*m;k+=2)
		{
			scanf("%d %d",&a,&b);
			edge[k].to=b;
			edge[k].next=head[a];
			head[a]=k;
			edge[k+1].to=a;
			edge[k+1].next=head[b];
			head[b]=k+1;
		}
		int count=0;
		for(i=1;i<=n;i++)
		{
			if(!visit[i])
			{
				dfs(i);
				count++;
			}
		}
		printf("%d\n",count-1);
		scanf("%d",&n);
	}



//system("pause");
return 0;
}

hdoj1162

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1162
又是一道MST,只不过边权是浮点数,切需自己计算

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
typedef struct Point{
	double x;
	double y;
}Point;
typedef struct Dist{
	int pre;
	double dist;
}Dist;
double map[104][104];
double dis(double x1,double y1,double x2,double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void prim(Dist dist[],bool visit[],int n)
{
	int i,j;
	visit[1]=true;
	dist[1].dist=0;
	for(i=2;i<=n;i++)
	{
		dist[i].dist=map[1][i];
		dist[i].pre=1;
		visit[i]=false;
	}
	for(i=1;i<=n-1;i++)
	{
		double min=10000000;
		int k=0;
		for(j=1;j<=n;j++)
			if(!visit[j] && dist[j].dist<min)
			{
				min=dist[j].dist;
				k=j;
			}
		if(k==0) break;
		visit[k]=true;
		for(j=1;j<=n;j++)
		{
			if(!visit[j] && map[k][j]<dist[j].dist)
			{
				dist[j].dist=map[k][j];
				dist[j].pre=k;
			}
		}
	
	}
	return;
}
int main()
{
	int n,i,j;
	while(scanf("%d",&n)!=EOF)
	{
		Point point[101];
		bool visit[102];
		memset(map,0,sizeof(map));
		memset(visit,0,sizeof(visit));
		Dist dist[102];
		for(i=1;i<=n;i++)
		{
			scanf("%lf %lf",&point[i].x,&point[i].y);
		}
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				map[i][j]=dis(point[i].x,point[i].y,point[j].x,point[j].y);
		prim(dist,visit,n);
		double sum=0;
		for(i=1;i<=n;i++)
			sum+=dist[i].dist;
		printf("%.2lf\n",sum);
	}

//system("pause");
return 0;
}

hdoj1102——最小生成树

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1102
第一次写MST,小问题不断,开始的时候这道题是这么想的,因为已经修好的路不一定是原来最小生成树中的路,所以先把已经修好路的顶点加入A集合(最小生成树的集合),(假设有count个顶点已经修好路)并更新dist数组。那么接下来只要用prim算法对剩下的(n-count)个顶点继续构造最小生成树即可。但是不知何故,15MS时WA。。
看了一篇解题报告,发现他的做法是把已修好路的顶点之间的距离设为0,然后求出整张图的最小生成树。仔细想想,确实这样做思路更简单,而且代码实现也简单。因为已修好路的顶点间距离设为0,则接下来构造MST时可以保证这些修好的路必定在最小生成树中。(一种情况除外,当已经修好的路数量大于(n-1)时,会有几条长度为0的边被舍去,但是答案终归是0,并不影响正确性)
贴上AC代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Dist{
	int pre;
	int dist;
}Dist;
Dist dist[110];
int map[110][110];
int visit[110];
void prim(int n,int q)
{
	int i,j;
	{
		visit[1]=true;
		dist[1].dist=0;
		dist[1].pre=0;
		for(i=2;i<=n;i++)
		{
			dist[i].dist=map[1][i];
			dist[i].pre=1;
		}
	
	}
	for(i=1;i<=n-1;i++)
	{
		int min=10000,k=0;
		for(j=1;j<=n;j++)
		{
			if(!visit[j] && dist[j].dist<min)
			{
				min=dist[j].dist;
				k=j;
			}
		}
		if(k==0) break;
		visit[k]=true;
		for(j=1;j<=n;j++)
		{
			if(!visit[j] && map[k][j]<dist[j].dist)
			{
				dist[j].dist=map[k][j];
				dist[j].pre=k;
			}
		}
	}
	return;	
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int i,j,q;
		memset(visit,false,sizeof(visit));
		memset(map,0,sizeof(map));
		for(i=1;i<=110;i++)
			dist[i].dist=10000;
		
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				scanf("%d",&map[i][j]);
			}
		scanf("%d",&q);
	
		int a,b;
		for(i=1;i<=q;i++)
		{
			scanf("%d %d",&a,&b);
			map[a][b]=0;
			map[b][a]=0;
		}
		prim(n,q);
		int sum=0;
		for(i=1;i<=n;i++)
			sum+=dist[i].dist;
		printf("%d\n",sum);

	}

//system("pause");
return 0;
}

最小生成树——prim算法(邻接矩阵)

#include<stdio.h>
#include<stdlib.h>
typedef struct Dist{
	int pre;//这个点是连到集合A中哪个点的
	int dist;
}Dist;
Dist dist[n];//顶点数
int map[n][n];
int visit[n];
void prim(int dist[],int map[][])
{
	int i,j;
	dist[1].dist=0;
	for(j=2;j<=n;j++)
	{
		dist[j].dist=map[1][j];
		dist[j].pre=1;
		visit[j]=false;
	}
	visit[1]=true;
	for(i=1;i<=n-1;i++)
	{
		int min=INT_MAX;
		int k=0;
		for(j=1;j<=n;j++)
		{
			if(!visit[j] && dist[j].dist<min)
			{
				min=dist[j].dist;
				k=j;
			}
		}
		if(k==0) return;//无法从第一个结点扩展,即图不连通,返回
		visit[k]=true;
		for(i=1;i<=n;i++)
			if(!visit[i] && map[k][i]!=INT_MAX && map[k][i]<dist[i].dist)
			{
				dist[i].dist=map[k][i];
				dist[i].pre=k;
			}
	}
	return;
}
int main()
{




system("pause");
return 0;
}

hdoj1358

循环节:len-next[len]为长度为len的字符串的循环节,特别的,当k=len%(len-next[len])==0时,该字符串含有k个周期。但当k!=0时说明最后一个循环节未满。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char b[1000003];
int next[1000003];
void get_next()
 {
     int i = 0;
     int j = -1;
     next[0] = -1;
	 int len=strlen(b);
     while(i <len)
     {
         if(j == -1 || b[i] == b[j])
         {
             ++i;
             ++j;
             next[i] = j;
         }
         else
         {
             j = next[j];
         }
     }
	 return;
 }
int main()
{
	int count=0,n;
	scanf("%d",&n);
	while(n!=0)
	{

		count++;
		getchar();
		scanf("%s",b);
		get_next();
		printf("Test case #%d\n",count);
		for(int k=2;k<=n;k++)
		{
			int temp=k-next[k];
			int x=k/temp;
			if(k%temp==0 && x>1)
			{
				printf("%d %d\n",k,x);
			}
		}
		printf("\n");
		scanf("%d",&n);
	}
//system("pause");
return 0;
}

KMP模板(字符串都从0开始)(转载)

主串和模式串都从0开始
控制字符串输入起始指针:scanf(“%s”,s+1);
转载自:http://www.cnblogs.com/10jschen/archive/2012/08/19/2646381.html

void get_next(char b[], int *next)
 {
     int i = 0;
     int j = -1;
     next[0] = -1;
     int len_b = strlen(b);
     while(i < len_b - 1)
     {
         if(j == -1 || b[i] == b[j])
         {
             ++i;
             ++j;
             next[i] = j;
         }
         else
         {
             j = next[j];
         }
     }
 }
 
 int kmp_search(char a[], char b[], int next[])
 {
     int i = 0;
     int j = 0;
     int len_a = strlen(a);
     int len_b = strlen(b);
     while(i < len_a && j < len_b)
     {
         if(j == -1 || a[i] == b[j])
         {
             ++i;
             ++j;
         }
         else
         {
             j = next[j];
         }
     }
     if(j >= len_b)//j=len_b说明找到了模式串,此时如果ans++,j=next[j],则会继续寻找,ans保存找到的模式串个数
     {
         return i - len_b;
     }
     else
     {
         return -1;
     }
 }
Posted in KMP | Tagged |