文档章节

查找最长重复子字符串

huser_YJ
 huser_YJ
发布于 2014/09/22 16:38
字数 699
阅读 18
收藏 0
c

1.基本概念

子串:字符串 S 的子串 r[i..j] , i ≤ j ,表示 r 串中从 i 到 j 这一段,就是顺次排列 r[i],r[i+1],...,r[j] 形成的字符串。

后缀:后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串 r 的从 第 i 个字 符 开 始 的 后 缀 表 示 为 Suffix(i) ,也 就 是Suffix(i)=r[i..len(r)] 。

后缀数组:后缀数组 SA 是一个一维数组,它保存 1..n 的某个排列 SA[1] ,SA[2] , …… , SA[n] ,并且保证 Suffix(SA[i]) < Suffix(SA[i+1]) , 1 ≤ i<n 。也就是将 S 的 n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入 SA 中。

 

 

2.问题描述

给定一个文本文件作为输入,查找其中最长的重复子字符串。例如,"Ask not what your country can do for you, but what you can do for your 
country"中最长的重复字符串是“can do for you”,第二长的是"your country"。

 

3.解决思路

利用后缀数组。首先输入一个字符串到c[]中,例如“banana”,读入时我们队指针的数组a进行初始化,使得每个元素指向输入字符串的相应字符,则元素a[0]指向整个字符串,下一个元素指向从第二个字符开始的数组后缀,等等。对于前面的输入字符串,该数组能够表示下面这些后缀:

a[0]:banana
a[1]:anana
a[2]:nana
a[3]:ana
a[4]:na
a[5]:a

如果某个长字符串在数组a中出现两次,那么她将出现在两个不同的后缀中,因此我们队数组排序以寻找相同的后缀,下面将上面的数组a进行数组排序,结果如下

a[0]:a
a[1]:ana
a[2]:anana
a[3]:banana 
a[4]:na
a[5]:nana

然后我们就可以扫描数组,通过比较相邻元素来找出最长的重复字串,如上为"ana"

 

4.代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 5000000
char c[MAXN], *a[MAXN];


int comlen(char *p, char *q)
{
    int i = 0;
    while(*p && (*p++ == *q++))
    {
             i++;
    }
    return i;
}

int pstrcmp(const void *a, const void *b)
{
    return  strcmp(*(char* const*)a, *(char* const*)b); //这里的 *(char* const*)a中的a 为指向指针的指针,
}                                                       //首先(char* const*)a 将变量a强制转换成char类型的指向指针的const指针,
                                                        //然后用*进行 地址解引用 

 
int main()
{
    char ch;
    int i,n=0,maxlen=-1,maxi;
    
    while((ch = getchar()) != EOF && ch != '\n')
    {
              a[n] = &c[n];
              c[n++] = ch;
    }
    c[n]='\0';
    
    
    qsort(a, n , sizeof(char *), pstrcmp);

    
    for(i = 0;i < n-1; i++)
    {
          if(comlen(a[i], a[i+1]) > maxlen)
          {
                    maxlen = comlen(a[i], a[i+1]);
                    maxi = i;
          }
    }
    
    printf("%.*s\n", maxlen, a[maxi]);
    
    system("pause");
    return 0;
}


© 著作权归作者所有

huser_YJ
粉丝 2
博文 21
码字总数 28816
作品 0
武汉
私信 提问
JavaScript数据结构与算法(串)

KMP算法 例如一个字符串有30W个字符判断是否存在"I am Chinese". 类似这样的查找字符的毫无疑问需要使用. 算法由二个部分组成. 获取查找串的部分匹配表PMT 源串根据PMT进行回滚 回滚位数 = ...

fiveoneLei
2018/05/30
0
0
3. Longest Substring Without Repeating Characters - LeetCode

LeetCode Problems Solutions question description:问题描述 Given a string, find the length of the longest substring without repeating characters. 给定一个字符串,查找没有 重复字符......

才华惊动党中央
2017/08/17
0
0
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0
JavaScript 算法与数据结构 - javascript-algorithms

javascript-algorithms 包含了多种基于 JavaScript 的算法与数据结构。 每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 数据结构 数据结构是在计算机中...

匿名
2018/05/31
0
0
Leetcode_3. Find the longest substring without repeating characters

3. Find the longest substring without repeating characters Given a string, find the length of the longest substring without repeating characters. 给一个字符串,求出最长的无重复字......

gexin1023
2018/06/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

RocketMQ的事务投递

RocketMQ的事务投递 这是阿里的分布式事务图: 1、A服务先发送个Half Message给Brock端,消息中携带 B服务 即将要+100元的信息。 2、当A服务知道Half Message发送成功后,那么开始第3步执行本...

春哥大魔王的博客
18分钟前
1
0
Qt编写自定义控件31-面板仪表盘控件

一、前言 在Qt自定义控件中,仪表盘控件是数量最多的,写仪表盘都写到快要吐血,可能是因为各种工业控制领域用的比较多吧,而且仪表盘又是比较生动直观的,这次看到百度的echart中有这个控件...

飞扬青云
23分钟前
1
0
DisplayPort 迎来重大更新,数据带宽性能提高3倍

VESA宣布了他们对DisplayPort接口三年来的第一次重大更新。 与DP 1.4a相比,DisplayPort 2.0提供了三倍于DP 1.4a的数据带宽性能,支持超过8K的分辨率,更高的刷新率和更高分辨率的HDR,以及其...

linuxCool
30分钟前
1
0
《Linux就该这么学》2019年7月20日第八天上课笔记

du命令 du -sh /newFS/ 察看文件/文件夹数据占用量 SWAP 交换分区的设置 磁盘容量配额 RHEL 5/6 usrquota RHEL 7 quota 软硬连接 ln 软 指针指向inode 硬 建立新的inode RAID 0 1 5 1+0...

2lodoss
33分钟前
1
0
适合钱包应用开发的ERC20代币数据集

Erc20Tokens数据集包含超过1000种主流的以太坊ERC20代币的描述数据清单和图标,可用于钱包等区块链应用的开发,支持使用Java、Python、Php、NodeJs、C#等各种开发语言查询主流ERC20代币的相关...

汇智网教程
57分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部