Find the cycle section .

#include<stdio.h>
#include<string.h>
#define maxn 1000010
int next[maxn];
char s[maxn];
void getnext()
{
int j,k,len=strlen(s);
j=;
k=-;
next[]=-;
while(j<len)
{
if(k==-||s[j]==s[k])
{
j++;
k++;
next[j]=k;
}
else k=next[k];
}
}
int main()
{
int i,len,ff=;
while(scanf("%d",&len)!=EOF)
{
if(len==)
break;
scanf("%s",s);
getnext();
printf("Test case #%d\n",++ff);
/* for(i=1;i<=len;i++)
printf("%d ",next[i]);
printf("\n");*/
for(i=;i<=len;i++)
{
if(i%(i-next[i])==&&i!=(i-next[i]))
{
printf("%d %d\n",i,i/(i-next[i]));
}
}
printf("\n");
}
}

hdu1358 KMP More articles about

  1. hdu-1358(kmp)

    The question : Give you a length of n String , How many are there in all Xi—— from 0 Start to Xi The length of this character substring is a circular string , And output the maximum number of cycle sections : Their thinking : use kmp Of next Array , We from next The value of the array shows the word ...

  2. hdu1358 kmp Of next Array

    For each prefix of a given string S with N characters (each character has an ASCII code between 97 a ...

  3. HDU1358 KMP( The shortest cycle section )

    Period Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Subm ...

  4. HDU1358 Period —— KMP Minimum cycle section

    Topic link :https://vjudge.net/problem/HDU-1358 Period Time Limit: 2000/1000 MS (Java/Others)    Memory Lim ...

  5. [KMP Find the minimum cycle section ][HDU1358][Period]

    The question Find the number of all cycles greater than 1 The prefix of The maximum number of cycles and prefix position of solution Direct use KMP Find the minimum cycle section When satisfied i%(i-next[i])&&next[i]!=0 The number of prefix cycles is greater than 1 The minimum cycle section is i ...

  6. hdu1358 Period KMP

    Give a string , Find out all the substring lengths that can be used as its loop section utilize kmp The properties of mismatched arrays of , You can do it directly #include<stdio.h> #include<string.h> ; cha ...

  7. poj1961 &amp; hdu1358 Period【KMP】

    Period Time Limit: 3000MS   Memory Limit: 30000K Total Submissions: 20436   Accepted: 9961 Descripti ...

  8. HDU-1358 Period String problem KMP Algorithm Find the minimum cycle section

    Topic link :https://cn.vjudge.net/problem/HDU-1358 The question Give a string , For subscripts greater than 2 The elements of , How many minimum cycle sections are there Ideas For each element minloop, Just mold it carry ...

  9. hdu1358 Minimum cycle section , Maximum number of cycles KMP

    The question :       Give you a string , Let you find some strings , This string starts with the first letter , And he can be divided into 1 An upper loop substructure is enough , such as abcabcabc   So the current string is three abc Composed of , His A ...

Random recommendation

  1. project vue2.0 Fake takeout APP( 7、 ... and )

    ratings Evaluation list page implementation stay ratings.vue Component development First, introduce seller data : Writing template structure : Because the evaluation page has something written before star.vue Components , So again in ratings.vue Component Introduction : ...

  2. CDN Service Technology Architecture

    Preface In Bowen   Interpretation of the evolution of large websites    Talking about The whole family moved static files to CDN  It's all about CDN, Let's talk about it in detail this time CDN The architecture of brief introduction CDN It's a content distribution network built on the Internet , Rely on edge servers deployed everywhere ...

  3. iPhone:4.7 5.5 4 3.5 Corresponding to the screen size of each device, the corresponding pixels and App Online information

    Shared App Information You can access these properties from the App Details page in the App Informat ...

  4. Mysql Master slave synchronization error :1062 Error &#39;Duplicate entry &#39;1438019&#39;

    mysql Master slave synchronization error :1062 Error 'Duplicate entry '1438019' for key 'PRIMARY'' on query mysql This happens when the master and slave libraries synchronize 1062 L ...

  5. mysql use root It's no problem that other users can't start after the user starts

    Problem description : use root Account activation mysql after , In use mysql Users or other non users root The account doesn't work mysql Problem solving : By looking at mysql Of err journal , Find out Failed to open log (robert-b ...

  6. compile glibc-2.14 One of the things that came out of LD_LIBRARY_PATH No path bug

    ../configure --prefix=/home/zzhy/wd/software/glibc-2.14 error :checking LD_LIBRARY_PATH variable... cont ...

  7. Linux How to deal with insufficient disk space

    maintain Linux The server needs to be deleted frequently for normal use Linux System log generated by system operation and business environment debug Log files . Installation package, etc . This paper mainly describes how to clean up the business environment through script debug Log files and uploads or backup files ...

  8. TcxGrid Sqlite text type Show memo

  9. MySQL Crash Course #02# Chapter 3. 4 wildcard . Pagination

    Indexes See the table . The document operation Two things you have to know Who is responsible for the data presentation wildcard . It's not necessary Retrieve different rows Restrict result set . Pages to find Using database . Table full name A semicolon after the command is useful for many DBMS It's not necessary , But it didn't ...

  10. EBS SOA modify Web Service Parameters

    l Requirements describe When put PL/SQL Statement Load To ISG, Generate WSDL And after deployment , Need modification PL/SQL The Baotou declaration part of . For example, modify the parameter type of a procedure , Again Load, To regenerate the WSDL, Redeployment . We will find that PL ...