[hackerrank] 문자열 제목

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
", 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：
정규 표현 식 을 주 고 그의 길 이 를 L 로 만족 시 키 는 str 개 수 를 찾 아 보 세 요.L 은 크기 를 제한 하지 않 습 니 다.
 
Hyper Strings
Sample Input
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
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: 
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
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.
해명 거리
문자열 S 를 드 리 겠 습 니 다. 이 문자열 은 소문 자 'a' 와 'b' 로 만 구성 되 어 있 습 니 다.다음은 M 질문 동작 을 드 리 겠 습 니 다.
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.
=====================================================================
A* Search Challenges
PacMan - BFS
 
 

Participants: 376 
Max Score: 100 
Difficulty: Moderate
Solve Challenge
Pacman A*
 
 

Participants: 227 
Max Score: 100 
Difficulty: Moderate
Solve Challenge
Pacman - UCS
 
 

Participants: 228 
Max Score: 100 
Difficulty: Difficult
Solve Challenge
N Puzzle
 
 

Participants: 156 
Max Score: 15 
Difficulty: Difficult