1 简单题：
回文串
str中删除某个字母，剩余部分是一个回文： O（n）
KMP
http://hihocoder.com/problemset/problem/1082
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
int main(){
char tmp[10] = "marshtomp", rep[10] = "fjxmlhx";
vector<int> pre(10, -1);// pre[]
for(int i = 0, j = -1; ; i++, j++){
pre[i] = j;
while(j>=0 && tmp[j]!=tmp[i]) j=pre[j];
if(!tmp[i]) {pre[i] = 0; // a special handling for this question: re-match from the head
break;
}
}
char buf[1000], ans[1000];
while(gets(buf)){
for(int i = 0, j = 0; ; i++, j++){
if(!tmp[j]) buf[i-9]='#'; // tag the matched point
char c= buf[i];
if(c>='A' && c<='Z') c = c-'A'+'a';
while(j>=0 && c != tmp[j]) j = pre[j];
if(!buf[i]) break;
}
for(int i = 0, k = 0; ; i++){
if(buf[i]=='#') {
for(int j = 0; rep[j]; j++) ans[k++] = rep[j];
i += 8;
}
else ans[k++] = buf[i];
if(!buf[i]) break;
}
printf("%s\n", ans);
}
return 0;
}
扩展KMP
http://hihocoder.com/problemset/problem/1084
3 难题
Square Subsequences
Morgan and a string
首先贪心法：
- 每次找较小的
- 即a[i] = b[j]时，找较小那个后缀(min (a[i]=>suffix[i] , b[j]=>suffix[j+len(a)+1]
) 对应的队的元素)
4 其它题
count strings：
Hyper Strings
2 3
a
ab
Sample Output
7
Explanation
In the first example all the Hyper Strings are : "" (a string with no characters), "a", "ab", "aa", "aaa", "aba", "aab".
Two strings Game
2 2 5
ab
cd
Sample output
a
cd
Explanation of the example
Consider the position ("", "").
There are two different kinds of moves: either append the last letter to one of the strings, either to append the first one. If the first player behaves in the first way, then second player can just do the same for another string and win the game. So, the only
chance that remains for the first player is to append the first letter to one of the strings. Then, the second player can do the same. This way, after the first two moves we get ("a", "c"). Then there's no option for the first player than to append the second
letter to one of the strings. After this, there's only one move that will be made by the second player. Then, we get ("ab", "cd"). This way, is the position ("", "") is a losing one for the first player.
If we consider, for example, a position ("", "c"), the first player can make a move to make the position equal to ("a", "c"). After that, no matter what will the second player's move - ("ab", "c") or ("a", "cd"), the first will make the position ("ab", "cd")
and the game will be ended with her victory. So, the position ("", "c") is a winning one for the first player.
The first five winning positions in the lexicographical order, starting with the first one are: ("", "c"), ("", "cd"), ("", "d"), ("a", ""), ("a", "cd").
Pseudo-Isomorphic Substrings
abbabab
Sample Output #00
1
2
4
6
9
12
15
Explanation #00
The first character is 'a', the set is {a} hence 1.
The first 2 characters are 'ab', the set is {a, b, ab} but 'a' is pseudo-isomorphic to 'b'. So, we can remove either 'a' or 'b' from the set. We get {a,ab} or {b,ab}, hence 2.
Similarly, the first 3 characters are 'abb', the set is {a, ab, abb, b, bb} and as 'a' is pseudo-isomorphic to 'b', we have to remove either 'a' or 'b' from the set. We get {a,ab, abb, bb}, hence 4. and so on...
Find Strings
2
aab
aac
3
3
8
23
Sample Output:
aab
c
INVALID
Explanation:
For the sample test case, we have 2 strings "aab" and "aac".
S1 = {"a", "aa", "aab", "ab", "b"} . These are the 5 unique substrings of "aab".
S2 = {"a", "aa", "aac", "ac", "c" } . These are the 5 unique substrings of "aac".
Now, S = {S1 U S2} = {"a", "aa", "aab", "aac", "ab", "ac", "b", "c"}. Totally, 8 unique strings are present in the set S.
The lexicographically 3rd smallest string in S is "aab" and the lexicographically 8th smallest string in S is "c". Since there are only 8 distinct substrings, the answer to the last query is "INVALID".
Two Two
5
2222222
24256
65536
023223
33579
Sample Output
7
4
1
4
0
Explanation:
In following explanations group i-j is group of student from index i to index j (1-based indexing)
In first case only 2 is of form power of two. It is present seven times for groups 1-1,2-2,3-3,4-4,5-5,6-6,7-7
In second case 2,4 and 256 are of required form. 2 is strength of group 1-1 and 3-3, 4 is strength of group 2-2 and 256 is strength of group 3-5.
In third case 65536 is only number in required form. It is strength of group 1-5
In fourth case 2 and 32 are of forms power of 2. Group 1-2 has values 0,2 but its strength is 0, as first value is 0.
In fifth case, None of the group has strength of required form.
Letter Islands
2 islands in the string ababaewabaq.
Your task is to calculate the number of different substrings of string s, that produces exactly k islands in it.
海明距离
C l r ch: 修改字符串，将该字符串中的字符都改成 ch ，该字符串开始于 l ，结束于 r ；
S l1 r1 l2 r2: 交换两个字符串，第一个字符串开始于 l1 ，结束于 r1 。第二个字符串开始于 l2 ，结束于 r2；
R l r: 翻转字符串，该字符串开始于 l ，结束于r；
W l r: 输出字符串，该字符串开始于 l ，结束于r；
H l1 l2 len: 输出两个连续字符串的海明距离，两个字符串分别开始于 l1 和 l2 ，并且拥有相同的长度 len。
字符串从1开始索引。
输入格式:
第一行输入一个整数 N ，代表最初字符串的长度。
第二行输入初始的字符串 S 。
第三行输入一个整数 M ，代表一个有 M 个询问操作。
接下来的 M 行，每行输入一个询问操作。
输出格式:
如果询问操作是 W 或者 H ，那么输出该询问操作。
数据约束:
1≤N≤50000
1≤M≤75000
对于 W 询问操作：输出的总字符数不超过 2⋅106
对于 C 、 R 和 W 询问操作： 1≤l≤r≤N;字符 ch 是 a 或者 b
对于 S 询问操作： 1≤l1≤r1<l2≤r2≤N
对于 H 询问操作： 1≤l1,l2≤N; li+len−1≤N; 1≤len≤N.
Score: 15 Difficulty: Difficult