## 【hackerrank】字符串题目

2018年04月12日 ⁄ 综合 ⁄ 共 5021字 ⁄ 字号 评论关闭

# 1 简单题：

## 回文串

str中删除某个字母，剩余部分是一个回文： O（n）

## http://hihocoder.com/problemset/problem/1082

```#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
int main(){
char tmp = "marshtomp", rep = "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, ans;
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 难题

## Morgan and a string

• 每次找较小的

• 即a[i] = b[j]时，找较小那个后缀(min (a[i]=>suffix[i] , b[j]=>suffix[j+len(a)+1]
) 对应的队的元素)

# 4 其它题

## Hyper Strings

Sample Input
2 3

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

Sample input
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

Sample Input #00
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

Sample Input

aab
aac

23
Sample Output
aab

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

Sample Input
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

For example, if we have a string ababaewabaq the substring aba marks the positions 1, 2, 3, 4, 5, 8, 9, 10; that is XXXXXewXXXq (X denotes marked position). We can see 2 groups of contiguous positions, that is 2 islands. Finally, substring aba produces
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≤50000
1≤M≤75000

=====================================================================
A* Search Challenges

#### PacMan - BFS

Participants: 376 Max
Score:
100
Difficulty: Moderate

#### Pacman A*

Participants: 227 Max
Score:
100
Difficulty: Moderate

#### Pacman - UCS

Participants: 228 Max
Score:
100
Difficulty: Difficult

#### N Puzzle

Participants: 156 Max
Score:
15
Difficulty: Difficult