寻找两个串最长公共子串的高效算法 - 黑马程序员技术交流社区

//
// main.m
// 测试题10
//
// Created by Mike on 14-12-5.
// Copyright (c) 2014年 Mike. All rights reserved.
//
/*
10、找出多个字符串中的最大公共子字符串，如“nbitheimanb”和“itheia”的最大子串是：”ithei”。（C语言）
*/
#import <Foundation/Foundation.h>
#define MAXLEN 80
char *maxCommon(char *s, char *t)
{
char arr[MAXLEN][MAXLEN];//用arr存储所有的公共子串 arr[0]代表第一个子串
int len[MAXLEN]; //用len[i]存储arr[i]串对应的长度
int maxIndex,maxLen;//最长子串的索引maxIndex和最大长度maxLen
int slen = 0;
int tlen = 0;
char *p = s;
char *q = t;
int i=0,j=0,countp=0;
int counti;
//计算s和t的长度以串长短的为模式串
while(*p)
{
slen++;
p++;
}
p = t;
while(*p)
{
tlen++;
p++;
}
//p指向长的字符串q指向短的字符串
if(slen<tlen)
{
p = t;
q = s;
}
else
{
p = s;
q = t;
}
//将全部的公共串存入arr[][]同时存入长度len[]
while(*q)
{
char *q1 = q;//q1为模式串它是逐渐变化的如itheima->theima->heima->eima....
char *p1 =p; //p1为主串，在while(*p1)循环内部变化nbitheima->bitheima->itheima....
while(*p1)
{
if(*q1==*p1)
{
arr[i][j] =*p1;len[i]++;
j++;
p1++;
q1++;
if(!*q1)
{
arr[i][j]='\0';
break;
}
if(!*p1)
{
arr[i][j]='\0';
}
}
else
{
q1 =q;
if(j!=0)//如果a[i]已经存入公共串
{
arr[i][j]='\0';
i++;j=0;
}
p1 = p+(++countp);
while(*p1&&*q1!=*p1)//如果总是q1!=*p1 不断改变主串nbitheima->bitheima->itheima....
{
p1 = p+(++countp);
//printf("p1=%s\n",p1);
}
}
}
i++;
j=0;
//printf("-------------------------------------------\n");
countp = 0;
q++;
}
//得到最大串长对应的串序号
for(counti = 0;counti<i;counti++)
{
if(len[counti]>maxLen)
{
maxLen =len[counti];
maxIndex = counti;
}
}
return arr[maxIndex];
}
int main()
{
printf("最长公共子串是：%s\n",maxCommon("nbitheimanb","itheima"));
return 0;
}

复制代码

//3.定义一个求最大公共子字符串的函数
void maxChild(char str[],char str1[])
{
//4.定义两个指针变量，用于记录相同的起始地址
char *p,*q;
//5.定义两个整型变量，用于保存最大公共长度
int n=0,m=0;
//6.通过for循环来遍历第一个字符串
for(int i=0;i<strlen(str);i++)
{
//7.通过for循环遍历第二个字符串
for(int j=0;j<strlen(str1);j++)
{
//8.每次比较完两个字符串的公共部分后，都设置m=0
m = 0;
//9.判断两个字符串起始相同，只要一有相同的，就同步进行判断
if(str[i]==str1[j]&&str1[j]!='\0'){
//10.通过同步进行比较公共字符串
for(int k=0;str[k+i]!='\0'&&str1[k+j]!='\0'&&str[k+i]==str1[k+j];k++)
{
//11.记录公共字符个数和第一个匹配的地址
m++;
p = &str[i];
}
if(m>n)
{
//12.保存大地址，和最大个数
q = p;
n = m;
}
}
}
}
//13.判断是否有公共子字符串
if(n>0){
//14.进行输出最大公共子字符串
for(int i=0;i<n;i++){
printf("%c",*(q+i));
}
}else{
printf("没有公共子字符串");
}
}

复制代码

p = &str[i];

复制代码

for(int k=0;str[k+i]!='\0'&&str1[k+j]!='\0'&&str[k+i]==str1[k+j];k++)
{
//11.记录公共字符个数和第一个匹配的地址
m++;
// p = &str[i]; 放到下面会更好
}
p = &str[i];

复制代码