Chinaunix首页 | 论坛 | 博客
  • 博客访问: 626818
  • 博文数量: 108
  • 博客积分: 46
  • 博客等级: 民兵
  • 技术积分: 1279
  • 用 户 组: 普通用户
  • 注册时间: 2012-08-16 11:36
个人简介

坐井以观天

文章分类

全部博文(108)

文章存档

2014年(13)

2013年(90)

2012年(6)

分类: C/C++

2013-06-27 17:42:21


    该问题来源于《编程珠玑》,解决的思想是用后缀数组,代码如下所示。
  1. /* Copyright (C) 1999 Lucent Technologies */
  2. /* From 'Programming Pearls' by Jon Bentley */

  3. /* longdup.c -- Print longest string duplicated M times */

  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <stdio.h>

  7. int pstrcmp(char **p, char **q)
  8. {
  9.     return strcmp(*p, *q);
  10. }

  11. int comlen(char *p, char *q)
  12. {    int i = 0;
  13.     while (*p && (*p++ == *q++))
  14.         i++;
  15.     return i;
  16. }

  17. #define M 2            //超过次数
  18. #define MAXN 5000000
  19. char c[MAXN], *a[MAXN];

  20. int main()
  21. { int i, ch, n = 0, maxi, maxlen = -1;
  22.     while ((ch = getchar()) != EOF) {
  23.         a[n] = &c[n];
  24.         c[n++] = ch;
  25.     }
  26.     c[n] = 0;
  27.     qsort(a, n, sizeof(char *), pstrcmp);
  28.     for (i = 0; i < n-M; i++)
  29.     {
  30.         if (comlen(a[i], a[i+M]) > maxlen)
  31.         {
  32.             maxlen = comlen(a[i], a[i+M]);
  33.             maxi = i;
  34.         }
  35.     }
  36.     printf("%.*sn", maxlen, a[maxi]);
  37.     return 0;
  38. }
    思路是这样的:数组a是一个指针数组,子数组a[i...i + M]表示M+1个字符串。由于数组是有序的,可以通过在第一个字符串i和最后一个字符串i+M上调用comlen函数快速确定这M+1个字符串共有的字符数目。
阅读(909) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~