• KMP,ACM集训

    目录

                                    831. KMP字符串

    输入格式

    输出格式

    数据范围

    输入样例：

    输出样例：

     解析：KMP模板

                            D - Cyclic Nacklace

    解析：KMP-next数组应用+循环字符串判断

                                    F - Power Strings

    解析：KMP-next数组应用+循环字符串判断

                                    H - Count the string

     解析：next数组理解

                                    J - String Problem

     解析：kmp求循环节，最小/最大表示法

                                    831. KMP字符串

    831. KMP字符串 - AcWing题库

    给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

    模式串 P 在字符串 S 中多次作为子串出现。

    求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

    输入格式

    第一行输入整数 N，表示字符串 P 的长度。

    第二行输入字符串 P。

    第三行输入整数 M，表示字符串 S 的长度。

    第四行输入字符串 S。

    输出格式

    共一行，输出所有出现位置的起始下标（下标从 00 开始计数），整数之间用空格隔开。

    数据范围

    1≤N≤105
    1≤M≤106

    输入样例：
    1. 3
    2. aba
    3. 5
    4. ababa
    输出样例：
    0 2

     解析：KMP模板

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14.  
    15. using namespace std;
    16. typedef long long LL;
    17. typedef unsigned long long ULL;
    18. const int N = 1e5 + 5, M = 1e6 + 5;
    19.  
    20. int n, m;
    21. string s, p;
    22. int ne[N];
    23.  
    24. int main() {
    25. 	cin >> n >> p >> m >> s;
    26. 	p.insert(0," ");
    27. 	s.insert(0," ");
    28. 	for (int i = 2, j = 0; i <= n; i++) {
    29. 		while (j && p[i] != p[j + 1])j = ne[j];
    30. 		if (p[i] == p[j + 1])j++;
    31. 		ne[i] = j;
    32. 	}
    33. 	for (int i = 1, j = 0; i <= m; i++) {
    34. 		while (j && s[i] != p[j + 1])j = ne[j];
    35. 		if (s[i] == p[j + 1])j++;
    36. 		if (j == n) {
    37. 			printf("%d ", i - n);
    38. 			j = ne[j];
    39. 		}
    40. 	}
    41. 	return 0;
    42. }

                            D - Cyclic Nacklace

    https://vjudge.net/contest/582298#problem/D

    CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, without any surprise, there are only 99.9 yuan left. he is too distressed and thinking about how to tide over the last days. Being inspired by the entrepreneurial spirit of "HDU CakeMan", he wants to sell some little things to make money. Of course, this is not an easy task.

    As Christmas is around the corner, Boys are busy in choosing christmas presents to send to their girlfriends. It is believed that chain bracelet is a good choice. However, Things are not always so simple, as is known to everyone, girl's fond of the colorful decoration to make bracelet appears vivid and lively, meanwhile they want to display their mature side as college students. after CC understands the girls demands, he intends to sell the chain bracelet called CharmBracelet. The CharmBracelet is made up with colorful pearls to show girls' lively, and the most important thing is that it must be connected by a cyclic chain which means the color of pearls are cyclic connected from the left to right. And the cyclic count must be more than one. If you connect the leftmost pearl and the rightmost pearl of such chain, you can make a CharmBracelet. Just like the pictrue below, this CharmBracelet's cycle is 9 and its cyclic count is 2:


    Now CC has brought in some ordinary bracelet chains, he wants to buy minimum number of pearls to make CharmBracelets so that he can save more money. but when remaking the bracelet, he can only add color pearls to the left end and right end of the chain, that is to say, adding to the middle is forbidden.
    CC is satisfied with his ideas and ask you for help.

    Input

    The first line of the input is a single integer T ( 0 < T <= 100 ) which means the number of test cases.
    Each test case contains only one line describe the original ordinary chain to be remade. Each character in the string stands for one pearl and there are 26 kinds of pearls being described by 'a' ~'z' characters. The length of the string Len: ( 3 <= Len <= 100000 ).

    Output

    For each case, you are required to output the minimum count of pearls added to make a CharmBracelet.

    Sample

    InputcopyOutputcopy
    3
aaa
abca
abcde
    		 
    0
2
5

    解析：KMP-next数组应用+循环字符串判断

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14.  
    15. using namespace std;
    16. typedef long long LL;
    17. typedef unsigned long long ULL;
    18. const int N = 1e5 + 100, M = 1e4 + 5;
    19. char str[N];
    20. int ne[N];
    21.  
    22. int main() {
    23. 	int T;
    24. 	scanf("%d", &T);
    25. 	while (T--) {
    26. 		//memset(str, 0, sizeof(str));//千万不要加这句，加了就会WA，我也不知道为什么
    27. 		scanf("%s", str + 1);
    28. 		int len = strlen(str + 1);
    29. 		int n = len;
    30. 		for (int i = 2, j = 0; i <= n; i++) {
    31. 			while (j && str[i] != str[j + 1])j = ne[j];
    32. 			if (str[i] == str[j + 1])j++;
    33. 			ne[i] = j;
    34. 		}
    35. 		int r = len-ne[len];
    36. 		if (ne[len] == 0) {
    37. 			printf("%d\n", len);
    38. 		}
    39. 		else {
    40. 			if (len % r == 0)
    41. 				printf("0\n");
    42. 			else
    43. 				printf("%d\n", r - len % r);
    44. 		}
    45. 	}
    46. 	return 0;
    47. }

                                    F - Power Strings

    Nefu字符串 - Virtual Judge (vjudge.net)

    Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

    Input

    Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

    Output

    For each s you should print the largest n such that s = a^n for some string a.

    Sample

    InputcopyOutputcopy
    abcd
aaaa
ababab
.

    1
4
3

    Hint

    This problem has huge input, use scanf instead of cin to avoid time limit exceed.

    Sponsor

    解析：KMP-next数组应用+循环字符串判断

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14.  
    15. using namespace std;
    16. typedef long long LL;
    17. typedef unsigned long long ULL;
    18. const int N = 1e7 + 5;
    19. int ne[N];
    20. char str[N];
    21.  
    22. int main() {
    23. 	while (scanf("%s",  str + 1) != EOF) {
    24. 		if (str[1] == '.')
    25. 			break;
    26. 		int n = strlen(str + 1);
    27. 		for (int i = 2, j = 0; i <= n; i++) {
    28. 			while (j && str[i] != str[j + 1])j = ne[j];
    29. 			if (str[i] == str[j + 1])j++;
    30. 			ne[i] = j;
    31. 		}
    32. 		int r = n - ne[n];
    33. 		if (n % r == 0)
    34. 			printf("%d\n", n / r);
    35. 		else {
    36. 			printf("1\n");
    37. 		}
    38. 	}
    39. 	return 0;
    40. }

                                    H - Count the string

     Nefu字符串 - Virtual Judge (vjudge.net)

    It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example:
    s: "abab"
    The prefixes are: "a", "ab", "aba", "abab"
    For each prefix, we can count the times it matches in s. So we can see that prefix "a" matches twice, "ab" matches twice too, "aba" matches once, and "abab" matches once. Now you are asked to calculate the sum of the match times for all the prefixes. For "abab", it is 2 + 2 + 1 + 1 = 6.
    The answer may be very large, so output the answer mod 10007.

    Input

    The first line is a single integer T, indicating the number of test cases.
    For each case, the first line is an integer n (1 <= n <= 200000), which is the length of string s. A line follows giving the string s. The characters in the strings are all lower-case letters.

    Output

    For each case, output only one number: the sum of the match times for all the prefixes of s mod 10007.

    Sample

    InputcopyOutputcopy
    1
4
abab
    		 
    6

     解析：next数组理解

    KMP中next数组的含义：0 - i 中的最大前缀后缀匹配

    预处理出next数组，可知每个next数组记录该串的最大前缀的长度（数值上等价于下标）。那么对于某一个长位n的子串s，除了 它本身和模板串匹配外，还有它的最大相同后缀。
    那么， ans = 本身的一个 + 最大相同后缀
    关于不重不漏，由于答案的第一部分的头部都是模板串的第一个字符，对不同长度一定不同，对第二部分，末尾字符不会相同，同样不会重复

     虽然next数组统计的时最大前后缀，但大的后缀有前缀，那么大后缀中的小后缀一定也有前缀

    注意：这道题中相同的部分不应该重叠，如：aaa 的答案为5

    所以当前后缀相交时，此部分不计入答案。

    好好理解理解！！！！

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14.  
    15. using namespace std;
    16. typedef long long LL;
    17. typedef unsigned long long ULL;
    18. const int N = 2e5 + 5, P = 131,mod= 10007;
    19. int n;
    20. char str[N];
    21. int ne[N];
    22.  
    23. int main() {
    24. 	int T;
    25. 	scanf("%d", &T);
    26. 	while (T--) {
    27.  
    28. 		scanf("%d%s",&n, str + 1);
    29. 		for (int i = 2, j = 0; i <= n; i++) {
    30. 			while (j && str[i] != str[j + 1])j = ne[j];
    31. 			if (str[i] == str[j+1])j++;
    32. 			ne[i] = j;
    33. 		}
    34. 		LL ans = 0;
    35. 		for (int i = 1; i <= n; i++) {
    36. 			if (ne[i] != 0)
    37. 				ans=(ans+1)%mod;
    38. 		}
    39. 		ans = (ans + n) % mod;
    40. 		printf("%lld\n", ans);
    41. 	}
    42. 	return 0;
    43. }

                                    J - String Problem

    Nefu字符串 - Virtual Judge (vjudge.net)

    Give you a string with length N, you can generate N strings by left shifts. For example let consider the string “SKYLONG”, we can generate seven strings:
    String Rank
    SKYLONG 1
    KYLONGS 2
    YLONGSK 3
    LONGSKY 4
    ONGSKYL 5
    NGSKYLO 6
    GSKYLON 7
    and lexicographically first of them is GSKYLON, lexicographically last is YLONGSK, both of them appear only once.
      Your task is easy, calculate the lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), its times, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.

    Input

      Each line contains one line the string S with length N (N <= 1000000) formed by lower case letters.

    Output

    Output four integers separated by one space, lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), the string’s times in the N generated strings, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.

    Sample

    InputcopyOutputcopy
    abcder
aaaaaa
ababab

    1 1 6 1
1 6 1 6
1 3 2 3

     解析：kmp求循环节，最小/最大表示法

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14.  
    15. using namespace std;
    16. typedef long long LL;
    17. typedef unsigned long long ULL;
    18. const int N = 1e6 + 5;
    19.  
    20. string str;
    21. int ne[N];
    22. int minrepresentation(string s) {
    23. 	int len = s.length();
    24. 	s = " " + s + s;
    25. 	int i = 1, j = 2;
    26. 	while (j <= len) {
    27. 		int k = 0;
    28. 		while (k < len && s[i + k] == s[j + k])k++;
    29. 		if (s[i + k] > s[j + k])i += k + 1;
    30. 		else j += k + 1;
    31. 		if (i == j)j++;
    32. 		if (i > j)swap(i, j);
    33. 	}
    34. 	return i;
    35. }
    36. int maxrepresentation(string s) {
    37. 	int len = s.length();
    38. 	s = " " + s + s;
    39.  
    40. 	int i = 1, j = 2;
    41. 	while (j <= len) {
    42. 		int k = 0;
    43. 		while (k < len && s[i + k] == s[j + k])k++;
    44. 		if (s[i + k] < s[j + k])i += k + 1;
    45. 		else j += k + 1;
    46. 		if (i == j)j++;
    47. 		if (i > j)swap(i, j);
    48. 	}
    49. 	return i;
    50. }
    51. int main() {
    52. 	while (cin >> str) {
    53. 		int mn = minrepresentation(str);
    54. 		int mx = maxrepresentation(str);
    55. 		str.insert(0, " ");
    56. 		int n = str.length();
    57. 		n--;
    58. 		for (int i = 2, j = 0; i <= n; i++) {
    59. 			while (j && str[i] != str[j + 1])j = ne[j];
    60. 			if (str[i] == str[j + 1])j++;
    61. 			ne[i] = j;
    62. 		}
    63. 		int r = n - ne[n];
    64. 		int ans = n % r ? 1 : n / r;
    65. 		printf("%d %d %d %d\n", mn, ans, mx, ans);
    66. 	}
    67. 	return 0;
    68. }

  • 相关阅读:
    FRI及相关SNARKs的Fiat-Shamir安全
    数据结构（8）树形结构——B树、B+树（含完整建树过程）
    windows 禅道一键安装包的升级
    云原生虚拟网络 tun/tap & veth-pair
    「运维有小邓」SIEM解决方案数据安全分析组件
    IOS OpenGL ES GPUImage 图像缩放 GPUImageTransformFilter
    利用Nginx可视化管理工具+Cpolar实现本地服务远程访问
    unity中方向的两种表示：欧拉角和四元数
    解决虚拟机克隆后IP和命名冲突问题
    刷题《剑指Offer》day12
  • 原文地址：https://blog.csdn.net/Landing_on_Mars/article/details/133044217