字符串匹配------回顾大一时的一份代码
说明
这是大一下的一份代码，当时不会用github，所以一直没妥善保存，直到最近清理360云盘时才重见天日，现在看来，这份代码水平很低，毕竟的当时也是刚刚接触C语言，当时作为一个非CS专业，指针甚至都不讲，基本都是自学。但记忆中，正是这份代码，让我体会到编程的快乐，开始了今后的编程之路。故此整理，以作纪念。
问题
这是当时的一个数模比赛题目，以下是原题：
1.1 背景资料与条件
给定一个DNA序列,这个序列只含有4个字母A、T、C、G,如S=”CTGTACTGTAT”.给定一个数值k,从S的第一个位置开始,取一连续k个字母的短串,称之为k-mer(如k=5,则此短串为CTGTA),然后从S的第二个位置,取另一k-mer(如k=5,则此短串为TGTAC),这样直至S的末端,就得到一个集合,包含全部k-mer.如对序列S来说,所有5-mer为{CTGTA,TGTAC,GTACT,TACTG,ACTGT,TGTAT}.这就是所谓的DNA序列的k-mer index问题.
通常这些k-mer需一种数据索引方法,可被后面的操作快速访问.例如,对5-mer来说,当查询CTGTA，通过这种数据索引方法,可返回其在DNA序列S中的位置为{1,6}.
1.2 需要解决的问题
现在以文件形式给定100万个DNA序列,序列编号为1-1000000,每个基因序列长度为100.
(1)要求对给定k,给出并实现一种数据索引方法,可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置.每次建立索引,只需支持一个k值即可,不需要支持全部k值.
(2)要求索引一旦建立,查询速度尽量快,所用内存尽量小.
(3)给出建立索引所用的计算复杂度,和空间复杂度分析.
(4)给出使用索引查询的计算复杂度,和空间复杂度分析.
(5)假设内存限制为8GB,分析所设计索引方法所能支持的最大k值和相应数据查询效率.
(6)按重要性由高到低排列,将依据以下几点,来评价索引方法性能
a.索引查询速度
b.索引内存使用
c.8G内存下,所能支持的k值范围
d.建立索引时间
记得当时说要用哈希表，但当时什么都不懂，直接暴搜了。
大意就是从下面的100万个数据中找出指定的基因串
当时的思路就是找到数据特征（这是当时的难点）然后分离，然后搜索就简单了
代码
# include "stdio.h"
# include "stdlib.h"//stdlib 头文件即standard library标准库头文件。stdlib.h里面定义了五种类型、一些宏和通用工具函数。
# include "time.h"
# define N 60
void PreIndex();//建立索引文本,目录文本
void DeepInfo1();//关键信息提取
void Search();//进行查找
long DeepInfo2();
int main()
{
//PreIndex();
//DeepInfo();
Search();
printf("结束");
return 0;
}
void PreIndex()
{
FILE * fpIndex, * fpCatalog, * fpsource1, * fpsource2;//定义四个指针，分别指向目标文件和两个附件个指针，分别指向目标文件和两个附件
fpCatalog = fopen("Catalog.txt","w");
fpIndex = fopen("Index.txt","w");//目标文件指针指向目标文件
if ((fpsource1=fopen("solexa_100_170_1.fa","r")) == NULL)
{
printf("Can't open the solexa_100_170_1.fa!\n");
getchar();
exit(-1);
}
//if做出判断的同时也指明了指针的指向
if ((fpsource2=fopen("solexa_100_170_2.fa","r")) == NULL)
{
printf("Can't open the solexa_100_170_2.fa!\n");
getchar();
exit(-1);
}
int i;
char ch;
char str[101];//VC中是不能在中间定义变量的，所以这个代码必须在c99标准下编译
for (i=0; i<500000; i++)//通过循环从第一个附件中读取50万个数据
{
while ((ch=fgetc(fpsource1)) && (ch<'A' || ch>'T'))
putc(ch,fpCatalog);
fputc(ch,fpIndex);
fgets(str,101,fpsource1);
fputs(str,fpIndex);
}
//while (ch=fgetc(fpsource1) && (ch<'A' || ch>'T'));这样是不对的，为什么说不清
//这一句好好理解，即读取的字符ASCII码不是ATCG时就不执行操作（注意while后面直接加分号表示不执行操作）
//执行while时包含了一个先对ch赋值的操作，每执行while文件位置指针都会后移一个，注意理解
for (i=0; i<500000; i++)//通过循环从第一个附件中读取50万个数据
{
while ((ch=fgetc(fpsource2)) && (ch<'A' || ch>'T'))
putc(ch,fpCatalog);
fputc(ch,fpIndex);
fgets(str,101,fpsource2);
fputs(str,fpIndex);
}
fclose(fpCatalog);
fclose(fpIndex);
fclose(fpsource1);
fclose(fpsource2);
}
void DeepInfo1()
{
FILE * fp,* fp0;
char ch;
int i = 0,j = 0;
fp = fopen("Catalog.txt", "r");
fp0 = fopen("DeepCatalog.txt", "w");
while ((ch = fgetc(fp)) && ch != EOF)
{
if (ch == '0')//1
{
ch = fgetc(fp);
if (ch == '0')//2
{
ch = fgetc(fp);
if(ch == '0')//3
{
ch = fgetc(fp);
if (ch == '0')//4
{
ch = fgetc(fp);
if(ch == '0')//5
ch = fgetc(fp);
if(ch == '0')//6
ch = fgetc(fp);
if(ch == '0')//7
{
ch = fgetc(fp);
ch = fgetc(fp);
do{
fputc(ch,fp0);
ch = fgetc(fp);
}while(ch != ' ');
fputc('\n',fp0);
}
}
}
}
}
}
fclose(fp);
}
void Search()
{
FILE * fpIndex = fopen("Index.txt","r");
FILE * fpDeepInfo = fopen("DeepInfo.txt","r");
int i = 0,j = -1,n = 0,m = 0, y = -1,v = 0,x = 0,key = 0,q = 0,w = 1;
char s[105],p[N];
int loc[100];//loc位location位置数组
printf("请输入长度为%d的模式串\n", N);
scanf("%s", p);
for(i=0; i<1000000; i++)
{
fgets(s,105 ,fpIndex);
while(q<(100-N+1))
{
if(s[n] == p[m])
{
n++;
m++;
if (m == N)
{
n = n - N + 1;
m = 0;
q = n;
j = n;
y++;
loc[y] = n;
}
}
else
{
n = n - m +1;
q = n;
m = 0;
}
}
n = 0;
q = 0;
m = 0;
if(j != -1)
{
if(i>=500000)
w = 2;
key = DeepInfo2(i);
printf(">read_170_%d_%d random_genome_10000000 %d 100\n", i+1, w, key);//1还是2，加判断
printf("{");
for(v=0;v<(y+1);v++)
printf("%d, ", loc[v]);
printf("\b\b}\n");
y = -1;
}
j = -1;
}
fclose(fpIndex);
fclose(fpDeepInfo);
}
long DeepInfo2(int i)
{
long key,j,a;
FILE * fp;
fp = fopen("DeepCatalog.txt","r");
a = i;
for (j=0;j<a;j++)
fscanf(fp,"%*ld",&key);
fscanf(fp,"%ld",&key);
fclose(fp);
return key;
}
//void IndexArray()
//{}
//void Search()
//{}
效果
可惜当时没有截图，只是复制了命令行内容：
CGAGCCTCCCAAAGGGTTATGTTCCTGAGATGGAAAAACCTACTCGTAACAAACCA<回车>
>read_170_127073_1 random_genome_10000000 3750232 100
{40}
>read_170_405491_1 random_genome_10000000 3750200 100
{8}
>read_170_686709_2 random_genome_10000000 3750228 100
{36}
>read_170_694436_2 random_genome_10000000 3750202 100
{10}
>read_170_740517_2 random_genome_10000000 3750218 100
{26}
>read_170_842871_2 random_genome_10000000 3750211 100
{19}
>read_170_882664_2 random_genome_10000000 3750224 100
{32}
可以看一下
果然，当初半个月，现在sublime下一个Ctrl+F就出来了。。。
后记
看着当初这份幼稚的代码，或许自己现在的水平已经不可同日而语了，但是，希望自己能保持当初的那份热爱和好奇心吧！
