首页 > 其他 > 详细

HDU 6761 Minimum Index(Lyndon分解)

时间:2020-10-13 22:56:28      阅读:53      评论:0      收藏:0      [点我收藏+]

题目链接
题意:
求一个字符串每个前缀的最小后缀的下标。
思路:
可以使用Lyndon分解来做。因为一个字符串进行Lyndon分解后,最小的后缀一定是最后一个Lyndon串。
在运行Duval算法求Lyndon分解的过程中,每次在最后加入一个字符,我们就可以求出以该字符结尾的前缀的最小后缀。

cin string t死我了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<vector> 
#include<iostream>
using namespace std;
#define Max_N 1000010
#define ll long long
const ll mod=1e9+7;
ll ans[Max_N];
char s[Max_N];
int n;
void duval() {
  int  i = 0;
  while (i < n) {
  	ans[i]=i;
    int j = i + 1, k = i;
    while (j < n && s[k] <= s[j]) {
      if (s[k] < s[j]){
        k = i;
        ans[j]=i;
    	}
      else{
       
        ans[j]=ans[k]+j-k; 
		k++;
    	}
      j++;
    }
    while (i <= k) {
      i += j - k;
    }
  }
}   
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s);
		n=strlen(s);
		duval();
		ll bas=1,sum=0;
		for(ll i=0;i<n;i++)
		{
		//	printf("%lld ",ans[i]+1);
			(sum+=(bas*(ans[i]+1))%mod)%=mod;
            (bas*=1112ll)%=mod;
		}
	//	printf("\n");
		printf("%lld\n",sum);
	}
}

HDU 6761 Minimum Index(Lyndon分解)

原文:https://www.cnblogs.com/2462478392Lee/p/13811297.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!