題意：
? ? ? 給你一個最長100W的串，然后讓你找到最小同構(gòu)子串，還有最大同構(gòu)子串的下標，最小同構(gòu)子串就是把字符串連接成一個環(huán)，然后選擇一個地方斷開，得到的一個ASCII最小的子串（求最大同理），得到兩個下標之后還要求兩個數(shù)，就是最小子串出現(xiàn)的次數(shù)，還有最大子串出現(xiàn)的次數(shù)，就是所有循環(huán)移位后的到的len個子串中最小子串出現(xiàn)了多少次？


思路：
? ? ? 求最小和最大小標這個可以用最小表示法來求（求最大就是把最小表示法稍微改一下），而求出現(xiàn)次數(shù)可以用KMP來求，出現(xiàn)次數(shù)等于最大周期數(shù)，為什么等于這個可以這樣想
abcabcabc 循環(huán)移位 bcabcabca 繼續(xù) cabcabcab 繼續(xù) abcabcabc三次就得到一個一樣的了，那么也就是說這個串中的任何循環(huán)移位串只要三次就會出現(xiàn)一樣的，本來總個數(shù)是len，每三個一樣是不是就是每個串出現(xiàn)len/3，這個三是不是就是我們KMP里面說的那個最小循環(huán)節(jié)。len/最小循環(huán)節(jié) 不就是最小循環(huán)節(jié)的周期數(shù)嗎？ so..直接KMP搞定次數(shù)，任何串出現(xiàn)的次數(shù)都是一樣的，最后再返回來說下最小表示法。


最小表示法可以直接求出來自小的（或者是最大的）循環(huán)移位串的首字母是的下標，
比如dabc的小標就是2（從1開始）
核心代碼很短
int GetMinId(char *str)
{
? ? int i = 0 ,j = 1 ,k = 0;
? ? while(i < len && j < len && k < len)
? ? {?
? ? ? ? int t = str[(i+k)%len] - str[(j+k)%len];
? ? ? ? if(!t) ++k;
? ? ? ? else?
? ? ? ? {
? ? ? ? ? ? t > 0 ? i = i + k + 1 : j = j + k + 1;
? ? ? ? ? ? if(i == j) j ++;
? ? ? ? ? ? k = 0;
? ? ? ? }?
? ? }
? ? return i < j ? i : j;


}


可以這么理解，先定義兩個變量i,j表示的都是前綴的下標，每次更新的時候我們把不滿足的下標往后更新，就是往后+，最后得到前面的那個小的就是答案，關(guān)鍵是為什么？
我是這樣想的
首先核心就是
if(t > 0) i = i + k + 1;
else j = j + k + 1;
這個地方是什么情況，比如i代表的串是 abcd ?j代表的串是abca此時的k肯定是3那么t>0這個時候i直接跳到d的后面，也就是i = i + k + 1,就是默認之間的都肯定不是答案，這個是關(guān)鍵，為什么之間的bcd都肯定不是答案的起點呢，原因是abcd 和abca比較的時候到k=3的時候發(fā)現(xiàn)不相等了，那么之前的一定是相等的，那么也就是說i的串的a和d之間的bcd當串首字母的時候肯定會被j的串a(chǎn)bca中的bc當首字母比下去，因為bcd<bca cd< ca d < a就是沒有必要再比較了，這個一開始可能很不容易理解，但是仔細想想會明白的，我說的是我自己的理解，也有可能有錯誤，還有就是提示一點，如果實在理解不了這個方法可以先寫一個暴力的，然后在想，我就是這么干的，順便給一個暴力的代碼吧，暴力的很多時候也可以過題目，只不過要看數(shù)據(jù)。


int GetMinId(char * str)
{
? ?int len = stelen(str);
? ?int i = 0 ,j = 1 , k = 0;
? ?while(i < len && j < len && k < len)
? ?{
? ? ? ?int t = str[(i+k)%len] - str[(j+k)%len];
? ? ? ?if(!t) ++k;
? ? ? ?else?
? ? ? ?{
? ? ? ? ? if(t > 0) i = j;
? ? ? ? ? j ++;
? ? ? ? ? k = 0;
? ? ? ? }
? ?}
? ?return i;
}




下面是hdu3374代碼


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


#define N 1000000 + 10


char str[N];
int next[N];


void GetNext(int m ,char *str)
{
? ? int j = 0 ,k = -1;
? ? next[0] = -1;
? ? while(j < m)
? ? {
? ? ? ? if(k == -1 || str[j] == str[k])
? ? ? ? next[++j] = ++k;
? ? ? ? else k = next[k];
? ? }
}


int GetMinId(int len ,char *str)
{
? ? int i = 0 ,j = 1 ,k = 0;
? ? while(i < len && j < len && k < len)
? ? {
? ? ? ? int t = str[(i+k)%len] - str[(j+k)%len];
? ? ? ? if(!t) ++k;
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? t > 0 ? i = i + k + 1 : j = j + k + 1;
? ? ? ? ? ? if(i == j) j ++;
? ? ? ? ? ? k = 0;
? ? ? ? }
? ? }
? ? return i < j ? i : j;
}


int GetMaxId(int len ,char *str)
{
? ? int i = 0 ,j = 1 ,k = 0;
? ? while(i < len && j < len && k < len)
? ? {
? ? ? ? int t = str[(i+k)%len] - str[(j+k)%len];
? ? ? ? if(!t) ++k;
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? t < 0 ? i = i + k + 1 : j = j + k + 1;
? ? ? ? ? ? if(i == j) j ++;
? ? ? ? ? ? k = 0;
? ? ? ? }
? ? }
? ? return i < j ? i : j;
}


int main ()
{
? ? int len;
? ? while(~scanf("%s" ,str))
? ? {
? ? ? ? len = strlen(str);
? ? ? ? GetNext(len ,str);
? ? ? ? int max = GetMaxId(len ,str) + 1;
? ? ? ? int min = GetMinId(len ,str) + 1;
? ? ? ? int c;
? ? ? ? if(next[len] && len % (len - next[len]) == 0)
? ? ? ? c = len / (len - next[len]);
? ? ? ? else c = 1;
? ? ? ? printf("%d %d %d %d\n" ,min ,c ,max ,c);
? ? }
? ? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的hdu3374最小表示法+KMP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。