博文
google代码搜索的标准KMP算法实现(2007-10-24 11:59:00)
摘要： 这是我在google 上的代码搜索出来的KMP算法我觉得写的还可以啊，自己拿来学学。
KMP.h#ifndef _KMP_H_
#define _KMP_H_
#ifdef __cplusplus
extern "C"
{
#endif /* __cplusplus */
extern int KMP(const char* strPattern, int len, const char* strTarget);
extern void KMP_end();
#ifdef __cplusplus
}
#endif /* __cplusplus */
#endif
申明一下。这个KMP是在字典程序中的一段。所以这个他用来申明的外部函数。KMP.cpp#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "kmp.h"
static int* prefix = NULL;
static int max_size = 0;
static void GetPrefixValue(const char* strPattern, int iPatternLen)
{
if (iPatternLen>max_size) {
prefix = (int*)realloc(prefix, iPatternLen*sizeof(int));
max_size = iPatternLen;
}
int i, j; /* i runs through the string, j counts the hits*/
i = 1; j = 0;
prefix[0] = 0;
while(i<iPatternLen)
{
if(s......
百度之星程序设计大赛初题目(2007-04-21 00:49:00)
摘要：1.百度语言翻译机 百度的工程师们是非常注重效率的，在长期的开发与测试过程中，他们逐渐创造了一套独特的缩略语。他们在平时的交谈、会议，甚至在各种技术文档中都会大量运用。
为了让新员工可以更快地适应百度的文化，更好地阅读公司的技术文档，人力资源部决定开发一套专用的翻译系统，把相关文档中的缩略语和专有名词翻译成日常语言。
输入要求：输入数据包含三部分：1. 第一行包含一个整数N(N<=10000)，表示总共有多少个缩略语的词条；2. 紧接着有N行的输入，每行包含两个字符串，以空格隔开。第一个字符串为缩略语（仅包含大写英文字符，长度不超过10字节），第二个字符串为日常语言（不包含空格，长度不超过255字节）；3. 从第N+2开始到输入结束为包含缩略语的相关文档（总长度不超过1000000个字节）。例：6PS 门户搜索部NLP 自然语言处理PM 产品市场部HR 人力资源部PMD 产品推广部MD 市场发展部百度的部门包括PS，PM，HR，PMD，MD等等，其中PS还包括NLP小组。样例：in.txt
输出要求：输出将缩略语转换成日常语言后的文档。（将缩略语转换成日常语言，其他字符保留原样）。例：百度的部门包括门户搜索部，产品市场部，人力资源部，产品推广部，市场发展部等等，其中门户搜索部还包括自然语言处理小组。样例：out.txt
2.饭团的烦恼 “午餐饭团”是百度内部参与人数最多的民间组织。同一个部门的、同一所大学的、同一年出生的、使用同一种型号电脑的员工们总是以各种理由组织各种长期的、临时的饭团。
参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们增进感情。但是，随着百度的员工越来越多，各个饭团的管理变得繁杂起来。特别是为了照顾员工们越来越挑剔的胃，饭团的点菜负责人的压力也越来越大。现在，这个任务就交给“百度之星”了，因为，你将要为所有的百度饭团设计一个自动点菜的算法。
饭团点菜的需求如下：1．经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近12元越好。2．菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。3．请谨记，百度饭团在各大餐馆享受8折优惠。
输入要求：1．输入数据第一行包含三个整数N，M......
蛇型矩阵的最简解(整体观察法)(2007-04-15 13:19:00)
摘要：蛇行矩阵
Problem蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。 Input本题有多组数据，每组数据由一个正整数N组成。（N不大于100） Output对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。 矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。 Sample Input5Sample Output1 3 6 10 152 5 9 144 8 137 1211
整体观察法思想:
先看输出;将它旋转45度你将看到;
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
其实这样也可以做解了。但是还有跟好的能看的很清楚的.你再让这组数往左边靠你将看到.
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
现在你可以看到什么?你看没行的最后一个元素.1 3 6 10 15.再往斜的继续看得到下行.2 5 9 14.再下.4 8 13.再下.7 12.最后.11.没色做为一行.你再摆下来。
1 3 ......