存档

文章标签 ‘编程珠玑’

最长重复子串

2012年6月25日 5 条评论

---

首先这是一个单字符串问题。子字符串R 在字符串L 中至少出现两次,则称R 是L 的重复子串。重复子串又分为可重叠重复子串和不可重叠重复子串,这里只是简单讨论最长可重叠的重复子串,给出基本算法和基于后缀数组的算法;关于后缀数组,这里也只是用最简单的形式实现,对于后缀数组的倍增算法和DC3算法的实现以及不可重叠重复子串的问题可参见算法合集之《后缀数组——处理字符串的有力工具》,以后再整理这几个问题。

最直接的方法就是子串和子串间相互比较,这样查看所有的子串对,时间复杂度为O(n^2),代码如下:

/* 最长重复子串 Longest Repeat Substring */

int maxlen;    /* 记录最长重复子串长度 */
int maxindex;  /* 记录最长重复子串的起始位置 */
void outputLRS(char * arr);  /* 输出LRS */

/* 最长重复子串 基本算法 */
int comlen(char * p, char * q)
{
	int len = 0;
	while(*p && *q && *p++ == *q++)
	{
		++len;
	}
	return len;
}

void LRS_base(char * arr, int size)
{
	for(int i = 0; i < size; ++i)
	{
		for(int j = i+1; j < size; ++j)
		{
			int len = comlen(&arr[i],&arr[j]);
			if(len > maxlen)
			{
				maxlen = len;
				maxindex = i;
			}
		}
	}
	outputLRS(arr);
}

阅读全文...

二进制思考(三):位排序、位索引(bit-map)简单举例

2012年3月1日 3 条评论

---

本节目的是利用上一节的知识加深理解《编程珠玑》中的一道位排序题目,位排序的思想比较简单,具体代码见参考文献吧,这里就不罗列了。

本文主要是写一下《The C Programming Language》第二章中一道非常简单的小题目,文中使用了三种方法,可以对比一下。

题目:编写函数squeeze(s1,s2),将字符串s1中任何与字符串s2中字符匹配的字符都删除。

分析:这道题目的注意点主要有两个,一是搜索匹配的字符,二是删除字符时后续字符的前移。这两方面都是有技巧在里面的,见代码

方法一:暴力搜索

#include<stdio.h>

void squeeze(char *s1, char *s2);
int ishave(char *s2, char c); // 判重

void main()
{
	char s1[] = "abcdefghigklmn";
	char s2[] = "helloworld";
	squeeze(s1,s2);
	printf("%s\n",s1);
}

void squeeze(char *s1, char *s2)
{
	int i = 0, j = 0;
	for(; s1[i] != '\0'; ++i)
	{
		if(!ishave(s2,s1[i]))
		{
			s1[j++] = s1[i];
		}
	}
	s1[j] = '\0';
}

int ishave(char *s2, char c)
{
	int i = 0;
	while(s2[i] != '\0')
	{
		if(s2[i] == c)
			return 1;
		++i;
	}
	return 0;
}

阅读全文...

交换两段连续(不连续)内存

2011年9月4日 没有评论

在《编程珠玑,第二版》和《编程之美》中都有关于交换两段连续的内存块的题目,而且非常经典,交换两段连续内存块的问题又可以延伸到交换两段不连续内存块的问题,无论是哪种情况都需要一个基本操作:反转内存块

反转内存时,比较简单,可以两个指针同时走,也可以一个指针,随意,实现如下:

01 // reverse the memory block
02 // goal: |12345| -> |54321|
03 void * reverseMemory(void *pMemory, const size_t memSize)
04 {
05     if(NULL == pMemory) return pMemory;
06     if(memSize < 2)        return pMemory;
07
08     char * beg = static_cast<char *>(pMemory);
09     char * end = beg + memSize -1;
10     for(; beg < end; ++beg, --end)
11     {
12         char memTmp = *beg;
13         *beg = *end;
14         *end = memTmp;
15     }
16     return pMemory;
17 }

其中,函数的两个形参分别为要反转内存的起始地址和内存块的大小。返回值类型为void*,指向反转内存块的起始地址。

实现了反转内存块这一基本操作后,我们就可以用它来交换两段连续的内存,从而解决类似“数组循环移位”的问题。具体算法在编程珠玑和编程之美中都有详细介绍,这里简单说一下:

假设有连续的内存块M和N形如:|----M---|--------N---------|

  1. 首先反转内存块M:M’=reverse(M)
  2. 反转内存块N:N’=reverse(N)
  3. 对整个内存块M’ N’进行反转:(M’N’)’ = NM


阅读全文...