Question

C/C++大数据处理：10Gtxt数据库文件

有一个10G的txt文件，以特定的格式存放着大量的数据库信息，请问：怎么写一个程序找到特定的字符串。
假如有这么一文件：大小为10G,存放着大量的文章，全部都是课文，现在找特定一句话，求一种方法，能最快找到特定的这句话。（这句话只在整个文档中出现一次）

关键是代码，一定要有能运行的代码。思路我也知道

Answer 1

10G 连一次导入内存都不行，而且你说的串除了出现1次没有其他特征，只能文件分块读入用KMP匹配
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1024*1024*10
int index_KMP(char *s,int n,char *t,int pos);
//利用模式串的t的next函数求t在主串s中的第pos个位置之后的位置的KMP算法（t非空，1<=pos<=Strlength(s)）。

void get_next(char * t,int * next);
//求模式串t的next函数的并存入数组next[]中。
int next[MAX];
int main()
{
char* s= (char*)malloc(MAX+1);
memset(s,0,MAX+1);
char t[256]={0},c;
printf("请输入检测字符串，以#号结尾");
int i=0;
while((c=getchar())!='#'&&i<256)
{
t[i++]=c;
}
fflush(stdin);
//strcpy(t,"2014-04-28 18:14:33,333");
get_next(t,next);
FILE* pf = NULL;
if((pf = fopen("1.txt","r"))==NULL){
printf("打不开文件！\n");
return 0;
}
int cur=0,n=0;
unsigned long long pos=0,sum=0;
while(!feof(pf))
{
int len = fread(s,1,MAX,pf);
sum+=len;
printf("读取第 %5d 次，长度 %5d ，总长:%ld\n",cur+1,len,sum);
n=index_KMP(s,MAX,t,pos);
if(n>0)
{
pos = n+cur*MAX;
break;
}
++cur;
}
fclose(pf);

free(s);
if(n!=0)
printf("\n模式串 t 在主串 s 中第 %ld 个位置之后。\n\n",n);
else
printf("\n主串中不存在与模式串相匹配的子串!\n\n");

}

int index_KMP(char *s,int n,char *t,int pos)
//利用模式串的T的NEXT函数求t在主串s中（长度n)的第pos个位置之后的位置的KMP算法，（t非空，1<=pos<=Strlength(s)）.
{
int i=pos,j=1;
while (i<=n &&j<=(int)strlen(t))
{
if (j==0 || s[i]==t[j-1]) //继续进行后续字符串的比较
{
i++;
j++;
}

else j=next[j]; //模式串向右移动
}
if (j>(int)strlen(t)) //匹配成功
return i-strlen(t)+1;
else //匹配不成功
return 0;
}

void get_next(char *t,int *next)
//求模式串t的next函数的并存入数组next[]中。
{
int i=1,j=0;
next[0]=next[1]=0;
while (i<(int)strlen(t))
{
if (j==0 || t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}
}
替换文件名，每次读10M，我测试50M的1S搞定，因为寻找串可能再两次读取之间，完美的做法是后一次要把前一次的最后N个字符重新读取，N为寻找的子串长度，计算长度时需要特殊考虑，我简略了该种情况

Answer 2

算法考虑：(假设要找字符串：student123)

1. 每次读入固定数量的字符，比如10k，直到找到字符串或文件结束，最后一次有可能读入少于10k个字符；
   

2. 在读入的数据中查找要查找字符串的第1个字符's'，如找到则进行逐字符比较，遇到不同字符停止检测，直到比较完全相符

3. 如遇到疑似合法字符串处于跨区位置，需要将下一个10k读进来接着判断