hdu 1358 Period (kmp,求字符串的周期)

Posted by 111qqz on Wednesday, August 10, 2016

TOC

hdu 1358 题目链接

题意:给一个字符串,求这个字符串的每个前缀(包括本身)的能否由k个子串组成(K>1)

思路:和poj 2406 比较类似。。

结论:字符编号从0开始,如果又i%(i-next[i])==0,则i前面的 串为一个轮回串,其中轮回子串出现i/(i-next[i])次。

证明类似之前最小覆盖中的,不断的等价交换,两两相等…(这个证明在字符串这里总是遇到2333)

然而其实我。。。做的时候。。并没有想到去证明。。。而是打印出了nxt数组然后找规律求得2333.

之前一直觉得找规律不是什么拿的上台面的做法。。。但是今年打了几场多校。。尤其是电子科大的那场。。。我发现。。。其实有的题目的正解就是找规律,猜结论。。。

&nbs;

/* ***********************************************
Author :111qqz
Created Time :2016年08月11日 星期四 03时20分44秒
File Name :code/hdu/1358.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E6+7;
int nxt[N];
char a[N];
int n ;
void getnxt( char *s)
{
    int i = 0 ;
    int j = -1;	
    nxt[0] = -1;
    int n = strlen(s);
    while (i<n)
    if (j==-1||s[i]==a[j]) nxt[++i]=++j;
    else j = nxt[j];
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    int cas = 0 ; 
    while (~scanf("%d",&n))
    {
        if (n==0) break;
        printf("Test case #%d\n",++cas);
        scanf("%s",a);
        getnxt(a);
//	    for ( int i = 0 ; i <= n ; i++  ) printf("nxt[%d]:%d\n",i,nxt[i]);
        for ( int i = 1 ; i <= n ; i++)
        {
        if (nxt[i]==0) continue; //因为题目要求k>1
        int tmp = i-nxt[i];
        if (i%tmp==0)
            printf("%d %d\n",i,i/tmp);
        }
        printf("\n");
    }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付