描述

最小表示法的问题原型

证明

a串，b串的长度相同，在a串后面补一条a串，b串同理
如果不补串的话要取膜
用下标i表示a串的某个位置，j表示b串的，计数k=0，起始i=j=0
比较a[i+k]==b[j+k]，若相等，k++
若a[i+k]<b[j+k],则j=j+k+1 k=0 重复上一步
最后若a串，b串相同，就会在某个i，j，发现以后一个串的长度，a与b是相同的
最小表示法的问题原型

输入

5
abaab
aabab

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
int getmin(char s[],int len)
{
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len)
    {
        int t=s[(i+k)%len]-s[(j+k)%len];
        if (!t) k++;
        else
        {
            if (t>0) i+=k+1;
            else j+=k+1;
            if (i==j) j++;
            k=0;
        }
    }
    return min(i,j);
}
int main()
{
    char s1[10],s2[10];
    int n;
    cout<<"puts in the lenth of string"<<endl;
    cin>>n;
    cout<<"puts string a"<<endl;
    cin>>s1;
    cout<<"puts string b"<<endl;
    cin>>s2;
    int k1=getmin(s1,n);
    int k2=getmin(s2,n);
    bool same=1;
    int len=0;
    for(;len<n ; len++){
        if(s1[(k1+len)%n]!=s2[(k2+len)%n]){
            same=0;break;
        }
    }
    if(same)printf("a is same as b\n");
    else printf("a is not same as b\n");
    return 0;
}