hdu 2609 How many 最大最小表示板题

缘起

字符串的最大最小表示算法. 学习一下. hdu 2609 How many

分析

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
给你n串项链(n < 10000), 每串项链的珠子个数<=100 ,请计算有多少种不同的项链. 这里不同的定义是如果
2串项链旋转之后一样则称这两串项链相同. 

【输入】
多样例, 每个样例是一个n(2<=n<=10000), 然后n行每行都是长度一样的01串

【输出】
每个样例输出多少种不同项链

【样例输入】
4
0110
1100
1001
0011
4
1010
0101
1000
0001

【样例输出】
1
2

【限制】
1s

这是字符串最大最小表示的板题. 首先讲一下 最大最小表示这个算法.

最小表示法在解决判断“同构”一类问题中有很大作用。而所谓的”同构问题”如下

1
2
3
4
5
循环同构问题：给出两个长度相等的串：s1 = “babba”和s2 = “bbaba”，其中两者均看成环状的，
即首尾是相接的，
问：从s1的哪里断开可以得到和s2一样的串或者两者不会相同？

对于本例就是从s1的第2个字符’a’后面断开，可以得到与s2一样的串。这个问题就是同构问题。

对于上述问题, 显然有以下暴力算法

1
2
朴素算法(O(nm))：即尝试s1的n个断开点，与s2进行比较，如果相同则找到同构位置，否则找不到。
该算法仅适用于n, m规模较小情况，对于n, m 都在10000规模的长度，明显速度太慢。

第二种算法是 kmp

1
2
3
模式串是s2, 文本串是s1+s1, 但是第二个s1去掉最后那个字符(最多从最后那个字符处断开之后同构, 最多能匹配
到倒数第2个字符处,所以第二个s1不需要最后那个字符).
复杂度是 O(N+M). 是一款优秀的判断字符串同构的算法.

其实有一种好简单的办法. 就是这里要讲的最大最小表示. 令 u=s1+s1, 第二个s1的最后那个字符不要, 同样, 令v = s2+s2, 其中第二个s2的最后那个字符不需要. 则如果s1和s2同构的话, 则考虑s1和s2的最小表示 ms1和ms2。

1
2
3
4
5
6
定义: 
对于字符串s[0,...,len-1], 它的最小表示ms(0<=ms<len)的意思是 s[ms,..,len-1,0,..,ms-1]是下面的
len个字符串集合中字典序最小的那个, 如果存在多个, ms是最小的那一个, 例如 s="aaaa", 则字典序都是一样
的,则 ms=0
{s[k,...,len-1,0,..,k-1] : 0<=k<len}
在下文中, 用s+i表示从s[i]开始, 长度为len的字符串, 而不是表示一个字符

则只需要看看S1[ms1,…,ms1+len-1] 和 S2[ms2,…,ms2+len-1] 是否相同。令 i = 0, j = 0 分别是指向S1和S2的指针. 则开始比较, 即

1
2
i = j = k = 0
while(k<len && S1[i+k]==S2[j+k]) k++

则一旦在k处失配的话, 即

1
2
3
4
S1[i] = S2[j]
S1[i+1]=S2[j+1]
...	...
S1[i+k-1]=S2[j+k-1]

现在kS2[j+k] （ S1[i+k] < S2[j+k] 同理分析）, 则我们就知道了

1
2
3
4
5
S1+i>S2+i
S1+i+1>S2+i+1
... ...
S1+i+k-1>S2+j+K-1
S1+i+k>S2+i+k

所以我们就知道了, 如果s1和s2同构的话，则S1+ms1和S2+ms2必然相等. 则S1+i,…,S1+i+k-1 都不会是S1的最小表示（因为他们能找到严格比自己小的, 这其实就是最大最小表示的核心!）. 所以 i 可以放心大胆的跳到 i+=k+1的位置去了。 同理, 如果S1[i+k] < S2[j+k] , 则j可以放心大胆的跳到 j+=k+1的位置去了.

一旦i+=k+1之后（其实就是将 S1+i,…,S1+i+k 这k+1个字符串给略去了, 但是并不能略去S2+j,..,S2+j+k这k+1个字符串, 因为并没有为他们找到严格比他们小的，所以k要重新归于0）, 则要再将 k 归于0, 重新比较 S1+i和S1+j, 即再次

1
2
3
i+=k+1;
k = 0;
while(k<len && S1[i+k]==S2[j+k]) k++;

如果s1和s2同构的, 则算法一定在i=ms1,j=ms2, k=len结束.

现在考虑一个实用性更强的问题——找到一个字符串的最小（大）表示. 

1
令 s[0,..,len-1] 是字符串, 请找到它的最小表示ms. 关于最小表示的定义在上面已经给出了.

令 s1 = s （即s[0,..,len-1]）, s2 = s+1（即 s[1,…,len-1,0]）, 则考虑s1和s2的上述同构问题. 因为s1和s2显然同构. 所以根据上面的讨论, 上面的算法可以求出ms来. 于是我们得到一块 字符串最大最小表示的板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int getmin(char *s, int len) // 函数返回s的最小表示
{
	int i = 0,j = 1, k = 0, t;
	while(i<len && j < len && k<len)
	{
		t = s[(i+k)%len] - s[(j+k)%len];
		if(!t)
		{
			++k;
			continue;
		}
		t>0?i+=k+1:j+=k+1;
		if(i==j) ++j;
		k = 0;
	}
	return min(i,j);
}

有了这块板子, 此题好切~

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 //#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
//#define LOCAL
const int maxn = 10005;
int n,len;
string ss[maxn],ss1[maxn];

int getmin(string &s)
{
	int i = 0,j = 1,k = 0, t;
	while(i<len && j<len && k<len)
	{
		t = s[(i+k)%len] - s[(j+k)%len];
		if (!t)
		{
			++k;
			continue;
		}
		t>0?i+=k+1:j+=k+1;
		if (i==j)
		{
			++j;
		}
		k = 0;
	}
	return min(i,j);
}

void kk(string &s, string &s1)
{
	s1 = "";
	int ms = getmin(s);
	s1 = s.substr(ms, len-ms);
	s1+=s.substr(0,ms);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	while(cin>>n)
	{
		for (int i = 0;i<n;i++)
		{
			cin>>ss[i];
			if (!i)
			{
				len = ss[i].size();
			}
			kk(ss[i],ss1[i]);
		}
		sort(ss1, ss1+n); // unique的前提是sort,忘了 wa了一发
		cout<< unique(ss1, ss1+n)-  ss1 <<endl;
	}
	return 0;
}

ac情况

Status Accepted
Time 109ms
Memory 4756kB
Length 884
Lang C++
Submitted 2019-10-30 16:11:16
Shared
RemoteRunId 31188596