hdu 3374 String Problem （最小表示法+KMP）

本文主要是介绍hdu 3374 String Problem （最小表示法+KMP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：http://acm.hdu.edu.cn/showproblem.php?pid=3374

1 题目要求给定一个字符串求出最小和最大表示的rank和出现的times。

利用最小/大表示法求出位置，然后利用KMP，next求出循环节，就能计算次数。

代码：

#include <stdio.h>
#include <string.h>const int N = 1000005;int n, next[N];
char s[N];void get_next(char *seq, int m) {next[0] = -1;int j = next[0];for (int i = 1; i < m; i++) {while (j >= 0 && seq[i] != seq[j + 1]) j = next[j];if (seq[i] == seq[j + 1]) j++;next[i] = j;}
}int getminsub(char *a) {int i=0, j=1, len=strlen(a), k=0;while(i < len && j < len && k < len) {if(i == j) j++;int ni = i + k, nj = j + k;if(ni >= len) ni -= len;if(nj >= len) nj -= len;if(a[ni] > a[nj])i  += k + 1, k = 0;else if(a[ni] < a[nj])j += k + 1, k = 0;else k++;}return i;
}int getmaxsub(char *a) {int i=0, j=1, len=strlen(a), k=0;while(i < len && j < len && k < len) {if(i == j) j++;int ni = i + k, nj = j + k;if(ni >= len) ni -= len;if(nj >= len) nj -= len;if(a[ni] < a[nj])i  += k + 1, k = 0;else if(a[ni] > a[nj])j += k + 1, k = 0;else k++;}return i;
}int main() {while (~scanf("%s", s)) {n = strlen(s);int min_v = getminsub(s);int max_v = getmaxsub(s);get_next(s, n);int k = n - (next[n - 1] + 1);printf("%d %d %d %d\n", min_v + 1, n % k? 1 : n/k, max_v + 1, n % k? 1 : n/k);}return 0;
}

这篇关于hdu 3374 String Problem （最小表示法+KMP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---