acmicpc.net 1786(kmp), 1305(kmp), 1157

https://www.acmicpc.net/problem/1786

kmp코드로 탐색해서 보여주면 된다. 가장 기초적인 kmp문제다.

# -*- encoding: cp949 -*-
def getpartialmatch(N):
    m = len(N)
    pi = [0]*m
    begin = 1; matched = 0
    while begin + matched < m:
        if N[begin + matched] == N[matched]:
            matched += 1
            pi[begin+matched-1] = matched
        else:
            if matched == 0:
                begin += 1
            else:
                begin += matched - pi[matched-1]
                matched = pi[matched-1]
    return pi

def kmp(H,N):
    n = len(H); m = len(N)
    ret = []
    pi = getpartialmatch(N)
    begin = 0; matched = 0
    while begin <= n-m:
        if matched < m and H[begin + matched] == N[matched]:
            matched += 1
            if matched == m:
                ret.append(begin)
        else:
            if matched==0:
                begin += 1
            else:
                begin += matched - pi[matched-1]
                matched = pi[matched-1]
    return ret

answer = kmp(raw_input(),raw_input())
print len(answer),'\n','\n'.join(map(lambda x:str(x+1),answer))

https://www.acmicpc.net/problem/1305

여태까지 만들어온 kmp소스의 pi배열은 다음과 같다. 

pi[i] == 입력받은 문자열 n[:i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이.

그러므로 답을 구하려면 

'입력받을 문자열의 길이-(접두사도되고 접미사도 되는 문자열의 최대 길이)==원본문자의 최소길이' 의 값을 구하면 된다. 

아래 코드의 n이 입력받을 문자열의 길이고, pi[n-1]는 입력받은 문자열의 길이에 대한 접두사도되고 접미사도 되는 문자열의 최대 길이이다. 그러므로 맨 아랫줄처럼 식을 써주면 답이 나온다.

# -*- encoding: cp949 -*-
def getpartialmatch(N,n):
    m = len(N)
    pi = [0]*n
    begin = 1; matched = 0
    while begin + matched < m:
        if N[begin + matched] == N[matched]:
            matched += 1
            pi[begin+matched-1] = matched
        else:
            if matched == 0:
                begin += 1
            else:
                begin += matched - pi[matched-1]
                matched = pi[matched-1]
    return pi

n = int(raw_input())
s = raw_input()
answer = []
pi = getpartialmatch(s,n)
print n-pi[n-1]

https://www.acmicpc.net/problem/1157

# -*- encoding: cp949 -*-
word_dict = dict([chr(65+i),0] for i in xrange(26))
for c in raw_input():
    if c.upper() not in word_dict:
        word_dict[c] = 1
    else:
        word_dict[c.upper()] += 1
word = sorted(word_dict.iteritems(),key=lambda x:x[1],reverse=True)
if word[0][1]==word[1][1]:
    print '?'
else:
    print word[0][0].upper()