String Problem

abcder
aaaaaa
ababab

1 1 6 1
1 6 1 6
1 3 2 3

题意:求循环串的字典序最大和最小的子串出现的次数和下标.

次数只要拿原串匹配一下统计就好了,下标用最小表示法找.

#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define maxn 1111111

char P[maxn], T[maxn<<1];
int n, m;
#define next Next
int next[maxn];

void get_next (char *p) {
	int t;
	t = next[0] = -1;
	int j = 0, m = strlen (p);
	while (j < m) {
		if (t < 0 || p[j] == p[t]) {//匹配
			j++, t++;
			next[j] = t;
		}
		else //失配
			t = next[t];
	}
}

int kmp () {
	get_next (P);
	int i = 0, j = 0, ans = 0;
	while (i < n && j < m) {
		if (j < 0 || T[i] == P[j]) {
			i++, j++;
		}
		else {
			j = next[j];
		}
		if (j == m) {
            ans++;
            j = next[j];
		}
	}
	return ans;
}

int min_max_express (char *s, int len,bool flag) {
    int i=0,j=1,k=0;
    while (i<len && j<len && k<len) {
        int t = s[(j+k)%len]-s[(i+k)%len];
        if (t==0) k++;
        else {
            if (flag) {
                if (t>0) j+=k+1;
                else i+=k+1;
            }
            else {
                if (t>0) i+=k+1;
                else j+=k+1;
            }
            if (i==j) j++;
            k=0;
        }
    }
    return min(i,j);
}

int main () {
    //freopen ("in.txt", "r", stdin);
	while (scanf ("%s", P) == 1) {
        m = n = strlen (P);
        for (int i = 0; i < 2*n-1; i++) T[i] = P[i%n];
        n <<= 1; n--;
        T[n] = 0;
        int ans = kmp ();
        printf ("%d %d %d %d\n", min_max_express (P, m, 1)+1, ans, min_max_express (P, m, 0)+1, ans);
	}
	return 0;
}

HDU 3374 (KMP 最小表示法)

原文：http://blog.csdn.net/morejarphone/article/details/51367745