黑马程序员技术交流社区

标题: 截取最大公共字符串奖励技术分 [打印本页]

作者: 恋梦 时间: 2015-3-20 10:01
标题: 截取最大公共字符串奖励技术分
本帖最后由 Micro 于 2015-3-20 10:10 编辑

      如题，在截取两个字符串中最大共公字符串，c语言或oc都可以                       例如字符串abcdefghijk和另一个字符串lmakfghmijlfg两个字符串中最大共公字符串是fgh
      奖励情况视答案方式奖励，后面解法相同的即作废（但可优化代码，哪怕稍有改动，但只改变变量名或方法名不算在内）。（可百度、必应、360等最低都是技术分起步，奖励情况上不封顶）                                                                            已向版主申请，以上奖励由版主发放。

                                                                                                            07版主宣

作者: wzboy 时间: 2015-3-20 10:06
本帖最后由 wzboy 于 2015-3-20 13:24 编辑

别人写的。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//先造一个常用函数
char* strsub( char const* pStrSrc, int iStart, int iLen )
{
if( !pStrSrc || iStart <  0 )
      return NULL;

int iStrLen = strlen( pStrSrc );

char* pStrRes = NULL;
if( iLen >= iStrLen - iStart )
{
      pStrRes = (char*)malloc( iStrLen - iStart + 1 );

      if( !pStrRes )
         return NULL;

      memset( pStrRes, 0,  iStrLen - iStart + 1 );

      strncpy( pStrRes, pStrSrc + iStart, iStrLen  - iStart );

      return pStrRes;
}
else
{
      pStrRes = (char*)malloc( iLen + 1 );

      if( !pStrRes )
         return NULL;

      memset( pStrRes, 0, iLen + 1 );

      strncpy( pStrRes, pStrSrc + iStart, iLen );

      return pStrRes;

}

}

char* maxComm( char* pStrLeft, char* pStrRight )
{
if( !pStrLeft || !pStrRight )
{
      return NULL;
}

char* pStrLess = NULL;
char* pStrMore = NULL;
char* pStrRes= NULL;

int iLeft = strlen( pStrLeft );
int iRight = strlen( pStrRight );

int iLess = ( iLeft <= iRight ) ? iLeft : iRight;

int i,j;

if( iLeft <= iRight )
{
      pStrLess = pStrLeft;
      pStrMore = pStrRight;
}
else
{
      pStrLess = pStrRight;
      pStrMore = pStrLeft;
}
char* pSt = NULL;

for( i = iLess; i > 0; i-- )
{
      for( j = 0; j <= iLess - i; j++ )
      {
         pStrRes = strsub( pStrLess, j, i );

         if( strstr( pStrMore, pStrRes ) )
            return pStrRes;

         free( pStrRes );
         pStrRes = NULL;
      }
}

return NULL;
}

int main( int argc, char** argv )
{
char* pStrLeft = "abcdeaasdd";
char* pStrRight = "asdabcadeaassdf";

puts( "max comm string between two strings" );
char* strMaxComm = maxComm( pStrLeft, pStrRight );
printf( strMaxComm );
puts( "" );

free( strMaxComm );
strMaxComm = NULL;

return 0;
}

作者: sixleaves 时间: 2015-3-20 10:11
首先先上最通俗的，暴力枚举方法，后面再上动态规划算法。时间复杂度为O(n^2),所以不能拥于比较长的字符串。
之所以用#import指令，是在xcode下，源文件为.m后缀文件。

#import <stdio.h>
#import <string.h>
int findLCS(char *s1, char *s2, char **s, char **e);
int main(int argc, const char * argv[]) {
// 解法1 暴力枚举法(两个字符串),反复调用即可求多个。
char * s = NULL, *e = NULL;
char *s1 = "nbitheimanb", *s2 = "ithei";
findLCS(s1, s2, &s, &e);
for (char *p = s; p <= e; p++)
putchar(*p);
puts("");
return 0;
}
// 返回最大子串的大小，s记录最大子串的起始位置，e记录最后一个位置
// 原本想用C++来写,比较简练，但是要求用C。
int findLCS(char *s1, char *s2, char **s, char **e) {
int len1 = strlen(s1), len2= strlen(s2);
char buf[100] = {0};
int max = -1; // 记录最大子串的大小
char *str = NULL;
char *p = len1 > len2? s2 : s1; // 指向两个串中最小串的第一个字符
if (p == s1) str = s2; else str = s1; // 最大子串肯定在最小两个串中，所以枚举它的位置进行判断即可。
for (char * ps = p; *ps; ps++) {
for (char * pe = ps; *pe; pe++) {
int len = pe - ps; // 计算枚举的子串大小
strncpy(buf, ps, pe - ps);
if (strstr(str, buf)) { // 查找是否存在该子串
if (len > max) {
max = len;
*s = ps; // 记录新的最大子串起始位置
*e = pe; // 结束位置
}
}
}
}
return max; // 返回最大子串大小。返回-1则不存在
}

复制代码

作者: wzboy 时间: 2015-3-20 10:34

sixleaves 发表于 2015-3-20 10:11
首先先上最通俗的，暴力枚举方法，后面再上动态规划算法。时间复杂度为O(n^2),所以不能拥于比较长的字符串 ...

貌似输出有问题，你把*s2=“ithei”；中的“ithei”里面插入任意一个字符，结果就不一样。

作者: sixleaves 时间: 2015-3-20 10:43

wzboy 发表于 2015-3-20 10:34
貌似输出有问题，你把*s2=“ithei”；中的“ithei”里面插入任意一个字符，结果就不一样。 ...

嗯是我字符串大小算错了。是闭区间，我大意算成半开区间了，只需要改动一个地方
把

int len = pe - ps + 1; // 计算枚举的子串大小
strncpy(buf, ps, pe - ps + 1);

复制代码

作者: sixleaves 时间: 2015-3-20 10:44
谢谢指正，修改后如下。

#import <stdio.h>
#import <string.h>
int findLCS(char *s1, char *s2, char **s, char **e);
int main(int argc, const char * argv[]) {
// 解法1 暴力枚举法(两个字符串),反复调用即可求多个。
char * s = NULL, *e = NULL;
char *s1 = "nbitheimanb", *s2 = "itheib";
findLCS(s1, s2, &s, &e);
for (char *p = s; p <= e; p++)
putchar(*p);
puts("");
return 0;
}
// 返回最大子串的大小，s记录最大子串的起始位置，e记录最后一个位置
// 原本想用C++来写,比较简练，但是要求用C。
int findLCS(char *s1, char *s2, char **s, char **e) {
int len1 = strlen(s1), len2= strlen(s2);
char buf[100] = {0};
int max = -1; // 记录最大子串的大小
char *str = NULL;
char *p = len1 > len2? s2 : s1; // 指向两个串中最小串的第一个字符
if (p == s1) str = s2; else str = s1; // 最大子串肯定在最小两个串中，所以枚举它的位置进行判断即可。
for (char * ps = p; *ps; ps++) {
for (char * pe = ps; *pe; pe++) {
int len = pe - ps + 1; // 计算枚举的子串大小
strncpy(buf, ps, pe - ps + 1);
if (strstr(str, buf)) { // 查找是否存在该子串
if (len > max) {
max = len;
*s = ps; // 记录新的最大子串起始位置
*e = pe; // 结束位置
}
}
}
}
return max; // 返回最大子串大小。返回-1则不存在
}

复制代码

作者: sixleaves 时间: 2015-3-20 10:48

wzboy 发表于 2015-3-20 10:34
貌似输出有问题，你把*s2=“ithei”；中的“ithei”里面插入任意一个字符，结果就不一样。 ...

我在修改下代码、还有一处有错的地方、但思路没错就是了、

作者: marswawa 时间: 2015-3-20 10:52
//char1和char2接收用户输入的两个字符串，res用来保存找到的最大公共字符串，max用来保存array数组中最大元素的值，key保存array中最大元素对应的键值，j用来保存res的索引。
      char char1[NUM]; char char2[NUM]; char res[NUM]; int max = 0; int key = 0; int j = 0;
      //提示用户输入数据。
      printf("请输入一个字符串：");
      //将得到的第一个数据赋值给char1.
      scanf("%s", &char1);
      //提示用户输入第二个数据。
      printf("请输入第二个字符串：");
      //将得到的第二个数据赋值给char2
      scanf("%s", &char2);
      //将char1和char2的长度单独抽出来。
      int len1 = strlen(char1); int len2 = strlen(char2);
      //获得最短的字符串赋值给minChar。
      char *minChar = len1<len2?char1:char2;
      //获得最长的字符串赋值给maxChar。
      char *maxChar = len1<len2?char2:char1;
      //用来保存要比较的两个字符串比对的结果：挨个扫描，遇到相等的则保存为1，下次循环则累加起来。
      int array[NUM];
      //双层循环对两个字符串挨个比较。
      for (int i = 0; i<strlen(minChar); i++) {
         for (int j = 0; j<strlen(maxChar); j++) {
            //如果相等则将比对结果保存到array中。
            if (minChar[i] == maxChar[j]) {
                  //首轮比对及较长字符串第一个元素比对相等的话直接赋值比对结果为1。
                  if (i == 0 || j == 0) {
                     array[j] = 1;
                  } else {
                     //记录比对结果并在上次比对计数的基础上+1用来表示连续比对相同的字符个数。
                     array[j] = array[j-1]+1;
                     array[j-1] = 0;
                  }

            }
         }
      }
      //利用for循环找到array中连续比对相同的最大字符串长度及对应的索引值。
      for (int i = 0; i<NUM; i++) {
         if (array[i]>max) {
            max = array[i];
            key = i;
         }
      }

      //利用key和max在maxChar中找到匹配成功的最大字符串添加到res中记录。
      for (int i = key-max+1 ; i<=key; i++) {
         res[j++] = maxChar[i];
      }
      //打印结果。
      NSLog(@"%s", res);

}

作者: sixleaves 时间: 2015-3-20 11:04
暴力搜索最终版本。有两个错误、一个是我创建的buf缓存数组、没有每次用时重新初始化，导致有垃圾数据。
一个是我把闭区间[a ,b] 的大小算成了 b - a，这是计算[a, b)半开区间的方法。改正后如下

#import <stdio.h>
#import <string.h>
int findLCS(char *s1, char *s2, char **s, char **e);
int main(int argc, const char * argv[]) {
// 解法1 暴力枚举法(两个字符串),反复调用即可求多个。
char * s = NULL, *e = NULL;
char *s1 = "nbitheimanb", *s2 = "mbitheib";
findLCS(s1, s2, &s, &e);
for (char *p = s; p <= e; p++)
putchar(*p);
puts("");
return 0;
}
// 返回最大子串的大小，s记录最大子串的起始位置，e记录最后一个位置
// 原本想用C++来写,比较简练，但是要求用C。
int findLCS(char *s1, char *s2, char **s, char **e) {
int len1 = strlen(s1), len2= strlen(s2);
char buf[100] = {0};
int max = -1; // 记录最大子串的大小
char *str = NULL;
char *p = len1 > len2? s2 : s1; // 指向两个串中最小串的第一个字符
if (p == s1) str = s2; else str = s1; // 最大子串肯定在最小两个串中，所以枚举它的位置进行判断即可。
for (char * ps = p; *ps; ps++) {
for (char * pe = ps; *pe; pe++) {
int len = pe - ps + 1; // 计算枚举的子串大小
memset(buf, 0, sizeof(buf));
strncpy(buf, ps, pe - ps + 1);
if (strstr(str, buf)) { // 查找是否存在该子串
if (len > max) {
max = len;
*s = ps; // 记录新的最大子串起始位置
*e = pe; // 结束位置
//printf("max = %d\n", max);
}
}
}
}
return max; // 返回最大子串大小。返回-1则不存在
}

复制代码

作者: keeganlee 时间: 2015-3-20 12:42
#import <Foundation/Foundation.h>

int main(int argc, const char * argv[]) {
@autoreleasepool {
      NSString *max=@"nbitheimazhenniubi";
      NSString *min=@"itheimaz";
      NSString *tempstr=nil;
      if (max.length<min.length) {
         tempstr=max;
         max=min;
         min=tempstr;
      }
for (int i=0; i<=min.length-1; i++) {
         for (int j=0; j<=i; j++) {
            tempstr=[min substringWithRange:NSMakeRange(j, min.length-i)];
            if ([max containsString:tempstr]) {
                  NSLog(@"The Max Substing is %@",tempstr);
                  NSLog(@"It's length is %lu",(unsigned long)tempstr.length);
                  goto finish;
            }
         }
      }

}
finish: return 0;
}
我觉得是最简单的时间复杂度o（n2）,空间复杂度o（1）

作者: yyx1992 时间: 2015-3-20 13:04
//请各位指点
#include <stdio.h>
void GetCommon(char *s1, char *s2);
int main()
{ //字符串1
char *s1 = "nbitheimazhenniubi";
//字符串2
char *s2 = "itheimaz";
//调用最大公共字符串函数
GetCommon(s1, s2);
printf("\n");
return 0;
}
void GetCommon(char *s1, char *s2)
{
//分别计算两个字符串的长度
int len1 = 0;
int len2 = 0;
//此处strlen和strcpy都不可以用，不知道为什么，只能这样做了
while (*(s1+len1)!=0)
{
      len1++;
}
while (*(s2+len2)!=0)
{
      len2++;
}
//保存最大公共字符串的长度
int maxlen = 0;
for(int i = 0; i < len1; i++)
      {
         for(int j = 0; j < len2; j++)
            {
               //找到了第一个相等的
               if(s1[i] == s2[j])
                  {
                     // 保存第一个相等的首地址
                     int as = i, bs = j, count = 1;
                     //查找最大相等长度
                     while(as + 1 < len1 && bs + 1 < len2 && s1[++as] == s2[++bs])                                  count++;
                     //如果大于最大长度则更新
                     if(count > maxlen)
                           {
                              maxlen = count;
                                 //打印输出
                                 for (int m =0; m<count; m++)
                                 {
                                    printf("%c",s1[i+m]);
                                 }
                              }
                  }
         }
      }

}

作者: 落后就要挨打 时间: 2015-3-20 19:37
在黑马上听毕老师讲java，感觉比C使用起来快捷多了。试着答答题。

class Compare
{
private String str1;
private String str2;
Compare(String str1,String str2)
{
this.str1 = str1;
this.str2 = str2;
}
public String maxcommon()
{
for(int L = str1.length();L>0;L--)
{
for(int j = 0;j+L<str1.length()+1;j++)
{
String str1_part = str1.substring(j,j+L);
if(str2.indexOf(str1_part) != -1)
{
return str1_part;
}
}
}
return null;
}
}
class Strcompare
{
public static void main(String[] args)
{
String result = new Compare("abcdefghijk","lmakfghmijlfg").maxcommon();
if(result != null)
System.out.println("最大公共字符串是：" + result);
else
System.out.println("没有公共字符串");
}
}

复制代码

作者: Kuaile天使 时间: 2015-3-20 21:27
恰巧自己的基础测试也是这题，贴出来，大家相互学习，嘿嘿。

#include <stdio.h>
int main()
{
//定义两个字符数组，用于保存两个不同的字符串
char str1[100] = "nbitheimanb";
char str2[100] = "itheia";
//定义整型变量o_pisition最大子串初始位置，o_length最大子串长度，c_pisition当前子串位置，c_length当前子串长度
//并初始化各个变量初始值为零
int o_pisition = 0,o_length = 0,c_pisition = 0,c_length = 0;
//遍历主串中的每个字符与子串对比
for(int i = 0;str1[i] != '\0';i++)
{
//遍历子串中的每个字符与主串对比
for(int j = 0;str2[j];j++)
{
//比较主串与子串中的字符是否相等
if(str2[j] == str1[i])
{
//定义整型中间变量temp_i和temp_j，用于保存i和j的值，声明t_length用于保存子串长度，并初始化为零
int temp_i = i;
int temp_j = j;
int t_length = 0;
//判断子串是否结束
while(str2[temp_j] != '\0')
{
//比较两字符是否相等
if(str2[temp_j++] != str1[temp_i++])
{
//不等则退出循环
break;
}
//相等则长度加一
t_length++;
}
//比较当前子串长度与历史子串长度
if(t_length >= c_length)
{
//若大于则保存当前子串位置，和字串长度
c_pisition = i;
c_length = t_length;
}
}
}
//比较当前长度与历史子串长度
if(c_length >= o_length)
{
//保存最大子串位置
o_pisition = c_pisition;
//保存最大子串长度
o_length = c_length;
}
}
//遍历字符串，找出最大子串
for(int i = o_pisition; i < o_pisition + o_length;i++)
{
//打印字符，拼接最大子串
printf("%c",str1[i]);
}
//华丽丽的换行
printf("\n");
return 0;
}

复制代码

作者: azen 时间: 2015-3-20 22:48

keeganlee 发表于 2015-3-20 12:42
#import

int main(int argc, const char * argv[]) {

赞哎~~~~~~~~~~~~~~~~~~~~膝盖请收下

作者: 随心i 时间: 2015-3-20 22:55
本帖最后由随心i 于 2015-3-21 22:08 编辑

public class StringTest4
{
public static void main(String [] args)
{
String str1 = "adcfgeheightkdeffcser";
String str2 = "theightyye";

String result =getMaxString(str1,str2);
System.out.println(result);
}

private static String getMaxString(String str1, String str2)
{
String max =null;
String min = null;
max=(str1.length()>str2.length()?str1:str2);
min=max.equals(str1)?str2:str1;
for (int i = 0; i < min.length(); i++)
{
for(int start=0, end=min.length()-i;end != min.length()+1;start++,end++)
{
String sub = min.substring(start,end);
if(max.contains(sub))
return sub;
}
}
return null;
}
}

结果：

作者: xsun 时间: 2015-3-21 00:08
本帖最后由 xsun 于 2015-3-21 00:16 编辑

本来中午在公司就看到这个问题，但在公司也没什么时间可研究，就下班之后才开始研究。
由于对oc不是太熟，虽然用oc也写出来了，但很多概念也是现学现用（视频还没看完），可能有的地方效率不够或者写法不规范希望老师指正！
因为涉及算法问题，所以基本上所有语言思路都差不多，我就先用比较熟的php写完才移植到oc的。
求最大公字串实际上和LCS算法差不多，只不过LCS是求公字符的（就是说不连续但在相同位置相等的）
LCS算法：http://blog.csdn.net/leohxj/article/details/6003430
通过LCS算法，很简单的通过代码构建了一个二维表，并将相同的位置标为1。
在这里，我们设：
x方向的字符串为：abcitheimacba
y方向的字符串为：cbaitheimaabc
得到如下表格：

根据LCS算法，斜线方向连续最长不为0的位置所对应的就是我们要求的最大公共字符串，既：itheima
在只考虑实现的情况下，用php很容易得出了结果（因为php代码不是我们需要的答案，作为附件上传，供参考）
但这种方式会将整个二维表穷举多次，为了优化效率，在移植到oc的时候，对其进行了一点小小的改进。
如果我们连续出现相同的字符串，第一位的位置填1，第二位位置填2...
得到了如下表格：

如图：如果我们能将7的位置记录下来，之后再通过7的点向左上方寻找，即可很轻松得到我们所要的结果。

/**
* By Abel|2015-03-21 00:06:17
*/
#import <Foundation/Foundation.h>
int main() {
@autoreleasepool {
NSString *xString = @"abcitheimacba";
NSString *yString = @"cbaitheimaabc";
// LCS表
NSMutableArray *map = [NSMutableArray new];
// 记录字符串的长度
NSUInteger xLength = [xString length];
NSUInteger yLength = [yString length];
// 存放最大元素的位置
NSNumber *maxLength = @0;
CGPoint point;
// 构建二维数组
for(int y = 0; y < yLength; y ++){
NSMutableArray *child = [NSMutableArray new];
// 当前y方向的char字符
NSString *yChar = [yString substringWithRange:NSMakeRange(y, 1)];
for(int x = 0; x < xLength; x ++){
// 当前x方向的char字符
NSString *xChar = [xString substringWithRange:NSMakeRange(x, 1)];
NSNumber *state = @0;
if([xChar isEqualToString:yChar]){
// 第一次无法获取，直接为1
if(x == 0 || y == 0){
state = @1;
}else{
// 左上方所存的数字 + 1
NSNumber *level = map[y - 1][x - 1];
state = @([level intValue] + 1);
}
// 更新记录
if(maxLength <= state){
maxLength = state;
point.x = x;
point.y = y;
}
}
[child addObject:state];
}
[map addObject:child];
}
NSString *maxString = @"";
// 向左上寻找字符串，因为连续相等，所以用xString或yString都是一样的
for(int i = [maxLength intValue]; i > 0; i --){
int index = point.x = (int)point.x - 1;
// 因为下标和我们统计用值差1，所以这里要+1
NSString *string = [xString substringWithRange:NSMakeRange(index + 1, 1)];
maxString = [string stringByAppendingString:maxString];
}
// 输出结果
NSLog(@"%@", maxString);
}
return 0;
}

复制代码

至此，基本就搞定了楼主所出的题目，由于对oc实在不熟悉，所以基本上用到一个类型就要各种查，虽然艰难，但还好没有白费一晚上。

1.php.zip

1.3 KB, 下载次数: 150

php实现

作者: 随心i 时间: 2015-3-21 22:10
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//求两个字符串的最大公共字符子串，如"abccade","dgcadde"的最大子串为"cad"
int GetCommon(char *s1, char *s2, char **r)
{
  int len1 = strlen(s1);
  int len2 = strlen(s2);
  int maxlen = 0;
  int i = 0, j = 0;

for (i = 0;  i < len1;  i++)
  {
for(j = 0; j < len2; j++)
  {
if (s1[i] == s2[j])
{
   int as = i, bs = j, count = 1;
   while((as + 1 < len1 )&& (bs + 1 < len2) && (s1[++as] ==s2[++bs]))
   count++;
   if (count > maxlen)
{
   maxlen = count;
   *r = s1 + i;
   }
}
  }
}
return  maxlen;
}
//--
int main()
{
char a[] = "abccadefgh";
char b[] = "dgcaddefgh";
char *r;
int len=0;
len = GetCommon(a, b , &r);
printf("Len is %d \n", len);
printf("Result is %s \n", r);
return 0;
}

作者: koala1122 时间: 2015-3-21 23:56

xsun 发表于 2015-3-21 00:08
本来中午在公司就看到这个问题，但在公司也没什么时间可研究，就下班之后才开始研究。
由于对oc不是太熟， ...

值得一看呀，:)oc还没怎么学呢，得看一会

作者: 发发呆骄傲 时间: 2015-3-23 15:08
#在这里快速回复#package String_Test; public class Test4 { public static void main(String[] args) { // TODO Auto-generated method stub String s1="dfsadfhellosd"; // System.out.println(Integer.toString(2)); String s2="dfhellodf"; System.out.println(getMaxSubstring(s1,s2)); } public static String getMaxSubstring(String s1,String s2){ for(int i=0;i<s2.length();i++){ for(int y=0,z=s2.length()-i;z!=s2.length()+1;y++,z++){ //System.out.println(s2.substring(y,z)); String temp = s2.substring(y,z); if(s1.contains(temp)){ return temp; } } } return ""; } }

作者: 发发呆骄傲 时间: 2015-3-23 15:10
package String_Test; public class Test4 { public static void main(String[] args) { // TODO Auto-generated method stub String s1="dfsadfhellosd"; String s2="dfhellodf"; System.out.println(getMaxSubstring(s1,s2)); } public static String getMaxSubstring(String s1,String s2){ for(int i=0;i<s2.length();i++){ for(int y=0,z=s2.length()-i;z!=s2.length()+1;y++,z++){ //System.out.println(s2.substring(y,z)); String temp = s2.substring(y,z); if(s1.contains(temp)){ return temp; } } } return ""; } }

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2