Theme Section_z.theme section-程序员宅基地

Description

It's time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are going to add some constraints to the rhythm of the songs, i.e., each song is required to have a 'theme section'. The theme section shall be played at the beginning, the middle, and the end of each song. More specifically, given a theme section E, the song will be in the format of 'EAEBE', where section A and section B could have arbitrary number of notes. Note that there are 26 types of notes, denoted by lower case letters 'a' - 'z'.

To get well prepared for the festival, the hosts want to know the maximum possible length of the theme section of each song. Can you help us?

Input

The integer N in the first line denotes the total number of songs in the festival. Each of the following N lines consists of one string, indicating the notes of the i-th (1 <= i <= N) song. The length of the string will not exceed 10^6.

Output

There will be N lines in the output, where the i-th line denotes the maximum possible length of the theme section of the i-th song.

Sample Input

    
    
     
      
     
     5
xy
abc
aaa
aaaaba
aaxoaaaaa

Sample Output

    
    
     
      
     
     0
0
1
1

     
     
      2 
     
     
      

     
     
      这个问题主要意思是要让你把给出的字符串分成前后中三部分，并且三部分要完全相同，不能重叠在一起
     
     
      我的做法：先找出三个部分的每个部分的最长长度；
     
     
      从第一个字符开始，逐步测试前后是否相等；若前后相等，那么再找中间是否有符合的字符串，这个时候就要借助kmp算法了
     
     
      具体代码如下
     
     
      
     
     
      #include <stdio.h>
#include <stdlib.h>
#include<string.h>
char a[10000005];
char b[10000005];
int next[10000005];
void getnext(char  *p){
    int i,j,k;
    next[0]=-1;
    j=0;
    k=-1;
    int len=strlen(p);
    while(j<len){
        if(k==-1||p[j]==p[k]){
            ++j;
            ++k;
            if(p[k]!=p[j]) next[j]=k;
            else next[j]=next[k];
        }
        else k=next[k];
    }
}
int main()
{
    int i,j,k;
    int num,m,n;
    int len;
    int l;
    int flag;
    int max,count;
    scanf("%d",&num);
    while(num--){
        scanf("%s",a);
        len=strlen(a);
        l=len/3;
        max=0;
        if(l>0){
            count=0;
            max=0;
            for(i=0;i<l;i++){
                count++;
                b[i]=a[i];
                flag=0;//puts(b);
                for(j=0;j<=i;j++){
                    if(b[j]!=a[len-count+j]){flag=1;break;}
                }
                if(flag==0){
                    getnext(b);
                    m=i+1;
                    n=0;
                    while(m<len-i-1&&n<=i){

                        if(n==-1||a[m]==b[n]){
                            ++m;
                            ++n;
                        }
                        else n=next[n];
                        if(n==i+1){
                            max=i+1;
                            break;
                        }
                    }
                }
                //else break;
            }
            memset(b,'\0',sizeof(b));
        }
        printf("%d\n",max);
    }
    return 0;
}

本文链接：https://blog.csdn.net/qq_32126633/article/details/50411070

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

PhpStrom2018的激活范式_phpstrom2018.2.3-程序员宅基地

文章浏览阅读409次。1：找到windows-》System32-》drivers-》etc-》host-》配置域名（0.0.0.0 account.jetbrains.com）2：打开浏览器http://idea.lanyus.com/ 获取注册码3：复制注册码，注册时切换至Activation Code选项4：OK。_phpstrom2018.2.3

3dmax渲染有噪点的六大原因及解决方案_3dmax噪点多怎么解决-程序员宅基地

文章浏览阅读261次。原因：环境阻光（AO）的设置不当，导致模型结构转变处产生过多的暗部阴影，从而使渲染图像呈现出颗粒感和模糊。原因：3dmax中的材质细分不够，影响渲染效果，导致图像出现颗粒感和噪点。原因：3dmax中的图像尺寸过低，导致渲染后的效果图呈现出颗粒感和噪点。原因：发光贴图和灯光缓存的设置不当，导致渲染图像出现颗粒感和噪点。原因：3dmax中的主光源灯光细分不够，导致渲染图像有颗粒感。原因：DMC采样的参数设置不合理，导致渲染图像出现噪点。按照这些设置，通常可以避免图像出现噪点。，从而避免渲染后的模糊和噪点。_3dmax噪点多怎么解决

前端渲染CSR和SSR的结合使用分析_next同时使用ssr与csr-程序员宅基地

文章浏览阅读1.2k次。我们都知道，以往的CSR（客户端浏览器渲染）多多少少会有一点点SEO问题，不只是SPA（单页面应用程序），只不过SPA的SEO问题比较严重，一般的前端项目有很多个页面，渲染的压力是分散的，所以页面渲染速度很快，基本够爬虫抓到很多内容，但SPA只有一个页面。而我们的SSR（服务器渲染）可以弥补像SPA项目的SEO（搜索引擎优化）不友好问题。但是它本身对比CSR也是有不足的。所以，为什么不可以结合它们两个的优点去进行使用呢？_next同时使用ssr与csr

2022-IOS-For-Fun_um-ios 2022-程序员宅基地

文章浏览阅读503次。2022 IOS Developer for funBasic stuffComputer Science fundamentalsMain parts of a computer system - CPU, memory, storageHow Operating System worksWhat is a databaseHow Internet worksGit version controlObject Oriented ProgrammingThe setupMacOSHomeb_um-ios 2022

PHP中的循环描述错误有哪些_PHP关于while循环中修改选取条件出现的错误-程序员宅基地

文章浏览阅读109次。业务需求是：读取某个表中每一行的的字段A、B、C的值如果C的值是0，就改成1或者2代码大概是这么写的：$query = "SELECT * FROM table WHERE C = 0";$result = mysqli_query($link, $query);if($result){while ($rows = mysqli_fetch_array($result)){if (判断条件为tru..._while循环报错php

ionic介绍-程序员宅基地

文章浏览阅读3.4k次。最近公司在使用ionic做混合APP，虽然是最后端，但是也查一下东西，介绍一下吧这是菜鸟教程的Ionic一.介绍ionic是一种老式的使用H5开发iOS和Android应用的方式,也可以使用新的语言React Native开发,当然对于H5实现复杂的或者交互性没有那么好的,就可以使用iOS和Android的插件实现;二.Ionic特点a.开发方面:1.ionic 基于Angular..._ionic

随便推点

vue基于element-ui的Select选择器实现的动态多级联动下拉选择_element-ui select 级联-程序员宅基地

文章浏览阅读2w次，点赞6次，收藏26次。demo地址代码如下：Html<div id="app"> <el-select v-for="(arrItem,key) in selectList" :key="key" v-model="selectArr[key]" filterable placeholder="请选择" value-key="value" @change="selected" @focu..._element-ui select 级联

LeetCode——76. 最小覆盖子串_leetcode最小覆盖子串-程序员宅基地

文章浏览阅读123次。76. 最小覆盖子串_leetcode最小覆盖子串

Oracle 常用语句_oracle查询导入目录常用语句-程序员宅基地

文章浏览阅读112次。https://download.csdn.net/download/u014096024/21109113oracle练习1.如何查询一个角色包括的权限 a.一个角色包含的系统权限 select * from dba_sys_privs where grantee='DBA'; b.一个角色包含的对象权限2.oracle究竟有多少种角色 (查询oracle中所有的角色，一般是dba) select * from dba_roles;3.查询o..._oracle查询导入目录常用语句