求字符串的最小正周期



#include <iostream>
#include <cstring>   
using namespace std;    
int main()  
{  
    int n;  
    char data[100];  
    cin>>n;  
    while(n--)  
    {  
        cin>>data; 
        int len=strlen(data);  
        for (int i=1;i<=len;++i)  
        {  
            if(len%i==0)  
            {  
                int flag=1;  
                for(int j=i;j<len;++j)  
                {  
                    if(word[j]!=word[j%i])  
                    {  
                        flag=0;  
                        break;  
                    }  
                }  
                if(flag)  
                {  
                    cout<<i<<endl; 
                    break;  
                }  
            }  
        }  
        if (n!= 0)  
            cout<<endl;  
    }  
    return 0;  
}  

                
例如：


上面这个函数是个周期函数！而且任何正有理数都可以做它的周期，但是却不存在最小的正有理数来做它的周期，所以这个函数没有最小正周期。
            
转载于:https://www.cnblogs.com/thg999/p/9927115.html

定义：设函数f(x)的定义域为D(f)，若存在一个不为零的常数T，使得对任意x∈D(f)，有(x±T)∈D(f)且f(x±T)=f(x)，则称f(x)为周期函数，其中使上式成立的常数T称为f(x)的周期。

通常，函数的周期是指它的最小正周期，但并不是所有周期函数都有最小正周期。特例如狄利克雷(Dirichlet)函数(任意正有理数都是它的周期，但此函数没有最小正周期)：



D(x)={1,0,x为有理数x为无理数

hdu 3746 （求串的最小正周期）

思路：KMP的next 数组
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define LL long long
#define M 100005
#define DEBUG puts("It's here!")
#define INF 1<<29
#define CLS(x,v) memset(x,v,sizeof(x))
#define FOR(i,a,n)  for(int i=(a);i<=(n);++i)

char s[M];
int next[M];
int getnext(char *s)
{
    int i=0,j=-1;
    int len=strlen(s);
    next[0]=-1;
    while(i<len)
    {
        if(-1==j||s[i]==s[j])
            {
                i++;j++;
                if(s[i]==s[j])
                    next[i]=next[j];
                else
                    next[i]=j;
            }
        else
            j=next[j];
    }
    int r=len-next[len];//循环节
    if(r==len)return len;//不存在循环节
    if(0==len%r)return 0;//是周期串
    else return r-(len%r);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        printf("%d\n",getnext(s));
    }
    return 0;
}