9249번: 최장 공통 부분 문자열

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

길이가 x인 공통 부분 문자열이 존재하는지 Rabin-Karp 알고리즘으로 확인 가능하다.
x에 대해 파라메트릭 서치를 한다.

$O(l\lg l)$

#include<cstdio>
#include<cstring>
#include<unordered_map>
using namespace std;
const long long mod = (1LL << 55) - 55;
char a[200001], b[200001];
int main() {
    scanf("%s%s", a, b);
    int low = 1, up = 2e5, mid, r = 2e5;
    while (low <= up) {
        mid = low + up >> 1;
        unordered_map<long long, int> mp;
        long long u = 0, v = 0, p = mod - 1;
        int i = 0;
        for (; i < mid; i++) p = p * 127 % mod, u = (u * 127 + a[i]) % mod, v = (v * 127 + b[i]) % mod;
        for (; a[i - 1]; i++) mp[u] = i, u = (u * 127 + a[i] + a[i - mid] * p) % mod;
        for (i = mid; b[i - 1]; i++) {
            if (mp.find(v) != mp.end()) { r = i; break; }
            v = (v * 127 + b[i] + b[i - mid] * p) % mod;
        }
        b[i - 1] ? low = mid + 1 : up = mid - 1;
    }
    b[r] = 0;
    printf("%d\n%s", up, b + r - up);
    return 0;
}

3033번: DVAPUT

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

Rabin-Karp 알고리즘으로 $O(l)$에 길이가 x인 같은 문자열이 두 번 나오는지 확인할 수 있다.
x에 대해 파라메트릭 서치를 한다.

시간복잡도는 $O(l\lg l)$

#include<cstdio>
#include<cstring>
#include<unordered_set>
using namespace std;
const long long mod = (1LL << 55) - 55;
int l;
char s[200001];
int main() {
    scanf("%d%s", &l, s);
    int low = 1, up = l, mid;
    while (low <= up) {
        mid = low + up >> 1;
        unordered_set<long long> st;
        long long p = mod - 1, t = 0;
        int i = 0;
        for (; i < mid; i++) t = (t * 127 + s[i]) % mod, p = p * 127 % mod;
        for (; i <= l; i++) {
            if (st.find(t) != st.end()) break;
            st.insert(t);
            t = (t * 127 + p*s[i - mid] + s[i]) % mod;
        }
        i > l ? up = mid - 1 : low = mid + 1;
    }
    printf("%d", up);
    return 0;
}

답은 lcp 길이의 최댓값이다.

시간복잡도는 $O(l\lg l)$

#include<cstdio>
#include<algorithm>
using namespace std;
int l, c[200000], a[200000], b[200000], sa[200000], sz, r;
char s[200001];
void csort() {
    for (int i = 0; i < sz; i++) c[i] = 0;
    for (int i = 0; i < l; i++) c[a[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i - 1];
    for (int i = l; i--;) sa[--c[a[b[i]]]] = b[i];
}
int main() {
    scanf("%d%s", &l, s);
    sz = max(l, 128);
    for (int i = 0; i < l; i++) a[i] = s[i], b[i] = i;
    csort();
    for (int i = 1, k; i <= l; i <<= 1) {
        k = 0;
        for (int j = l - i; j < l; j++) b[k++] = j;
        for (int j = 0; j < l; j++) if (sa[j] >= i) b[k++] = sa[j] - i;
        csort();
        k = 0;
        for (int j = 0; j < l; j++) b[sa[j]] = !j || sa[j - 1] + i < l && sa[j] + i < l && a[sa[j - 1]] == a[sa[j]] && a[sa[j - 1] + i] == a[sa[j] + i] ? k : ++k;
        for (int j = 0; j < l; j++) a[j] = b[j];
    }
    for (int i = 0, j = 0; i < l; r = max(r, j ? j-- : 0), i++)
        while (a[i] && s[i + j] == s[sa[a[i] - 1] + j]) j++;
    printf("%d", r);
    return 0;
}

9248번: Suffix Array

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

suffix array와 LCP를 구하는 문제

시간복잡도는 $O(l\lg l)$

#include<cstdio>
#include<cstring>
int n, sz, a[500000], b[500000], sa[500000], c[500000], lcp[500000];
char s[500001];
void csort() {
    for (int i = 0; i < sz; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[a[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i - 1];
    for (int i = n; i--;) sa[--c[a[b[i]]]] = b[i];
}
void SA() {
    sz = n > 128 ? n : 128;
    for (int i = 0; i < n; i++) a[i] = s[i], b[i] = i;
    csort();
    for (int i = 1, k; i <= n; i <<= 1) {
        k = 0;
        for (int j = n - i; j < n; j++) b[k++] = j;
        for (int j = 0; j < n; j++) if (sa[j] >= i) b[k++] = sa[j] - i;
        csort();
        k = 0;
        for (int j = 0; j < n; j++) b[sa[j]] = !j || sa[j] + i < n && sa[j - 1] + i < n&&a[sa[j]] == a[sa[j - 1]] && a[sa[j] + i] == a[sa[j - 1] + i] ? k : ++k;
        for (int j = 0; j < n; j++) a[j] = b[j];
    }
}
void LCP() {
    for (int i = 0, j = 0; i < n; lcp[a[i++]] = j ? j-- : 0)
        while (a[i] && s[i + j] == s[sa[a[i] - 1] + j]) j++;
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    SA();
    LCP();
    for (int i = 0; i < n; i++) printf("%d ", sa[i] + 1);
    printf("\nx");
    for (int i = 1; i < n; i++) printf(" %d", lcp[i]);
    return 0;
}

5982번: Forgotten Password

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

dp[i]: 0..i번째 글자를 정했을 때, 사전 순으로 가장 빠른 단어


아래 소스의 시간복잡도는 $O(l^2+l*nw*L_w)$ // $L_w$은 사전 내 단어의 최대 길이

#include<iostream>
#include<string>
using namespace std;
string w[1000], r[1001], p;
int l, nw;
int main() {
    cin >> l >> nw >> p;
    for (int i = 0; i < nw; i++) cin >> w[i];
    for (int i = 0; i < l; i++) if (!i || r[i] != "") {
        for (int j = 0; j < nw; j++) if (i + w[j].length() <= l) {
            int k = 0;
            for (; k < w[j].length(); k++) if (p[i + k] ^ '?' && p[i + k] ^ w[j][k]) break;
            if (k == w[j].length() && (r[i + k] == "" || r[i + k] > r[i] + w[j])) r[i + k] = r[i] + w[j];
        }
    }
    cout << r[l];
    return 0;
}

10747번: Censoring

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

$O(l)$

kmp 알고리즘을 돌리면서 패턴을 찾으면 j(아래 소스)를 패턴이 시작했던 지점에서의 j로 바꿔준다.
스택에 s의 문자를 하나씩 넣다가 패턴을 찾으면 최근 t개의 길이만큼 pop시킨다.

반복문이 끝난 후 스택에 있는 문자들을 모두 빼서 반대 순서로 출력하면 답.

#include<cstdio>
const int MXL = 1e6;
char s[MXL + 1], t[MXL + 1], r[MXL + 1];
int pi[MXL + 1] = { -1 }, a[MXL + 1], n;
int main() {
    scanf("%s%s", s, t);
    for (int i = 0, j = -1; t[i];) {
        if (j < 0 || t[i] == t[j]) pi[++i] = ++j;
        else j = pi[j];
    }
    for (int i = 0, j = 0; s[i];) {
        if (j < 0 || s[i] == t[j]) {
            r[n++] = s[i++];
            a[n] = ++j;
            if (!t[j]) j = a[n -= j];
        }
        else j = pi[j];
    }
    r[n] = 0;
    puts(r);
    return 0;
}

2703번: Cryptoquote

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


$O(tL)$

#include<cstdio>
int t;
char s[99], key[27];
int main() {
    for (scanf("%d", &t); t--;) {
        scanf(" %[^\n]%s", s, key);
        for (int i = 0; s[i]; i++) if (s[i] ^ 32) s[i] = key[s[i] - 'A'];
        puts(s);
    }
    return 0;
}

12780번: 원피스

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


$O(l_hl_n)$

#include<cstdio>
#include<cstring>
char h[100001], n[11];
char *p;
int r;
int main() {
    scanf("%s%s", h, n);
    p = h;
    while (p = strstr(p, n)) p++, r++;
    printf("%d", r);
    return 0;
}

$O(l_h+l_n)$

kmp 알고리즘을 쓴다.

#include<cstdio>
char h[100001], n[11];
int pi[11] = { -1 }, r;
int main() {
    scanf("%s%s", h, n);
    for (int i = 0, j = -1; n[i];) {
        if (j == -1 || n[i] == n[j]) pi[++i] = ++j;
        else j = pi[j];
    }
    for (int i = 0, j = 0; h[i];) {
        if (j == -1 || h[i] == n[j]) ++i, r += !n[++j];
        else j = pi[j];
    }
    printf("%d", r);
    return 0;
}

5582번: 공통 부분 문자열

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


$O(l^2)$

dp[i][j]: s1은 i번째 s2는 j번째를 끝으로 하는 최대 공통 문자열 길이
dp[i][j]= s1[i]==s2[j] 라면 dp[i-1][j-1]+1 아니면 0

#include<cstdio>
char s1[4002], s2[4002];
int dp[4001][4001], r;
int main() {
    scanf("%s %s", s1 + 1, s2 + 1);
    for (int i = 1; s1[i]; i++) {
        for (int j = 1; s2[j]; j++) if (s1[i] == s2[j]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            if (dp[i][j] > r) r = dp[i][j];
        }
    }
    printf("%d", r);
    return 0;
}

9251번: LCS

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


$O(nm)$

최장 공통 부분 수열의 길이를 구하는 문제이다.
dp[i][j]: 문자열 s1[1...i] 과 s2[1...j]의 최장 공통 부분 수열 길이
dp[i][j]=max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]+(s1[i]==s2[j]))

#include<cstdio>
#include<algorithm>
char s1[1002], s2[1002];
int dp[1001][1001], i, j;
int main() {
    scanf("%s %s", s1 + 1, s2 + 1);
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            dp[i][j] = std::max({ dp[i][j - 1],dp[i - 1][j],dp[i - 1][j - 1] + (s1[i] == s2[j]) });
    printf("%d", dp[i - 1][j - 1]);
    return 0;
}

1543번: 문서 검색

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


$O(ab)$ a, b: 문서, 단어 문자열 길이

앞에서부터 단어가 있으면 카운트하고 그 길이만큼 건너뛴다.
이는 그리디 알고리즘인데 건너뛰는 부분에 단어가 있어도 이것을 포함하는 해보다 항상 나쁘지 않기 때문에 쓸 수 있다.

#include<cstdio>
#include<cstring>
char s[2501], c[51];
int r, sl, cl;
int main() {
    scanf("%[^\n] %[^\n]", s, c);
    sl = strlen(s);
    cl = strlen(c);
    for (int i = 0; i < sl; i++) if (!strncmp(s + i, c, cl)) r++, i += cl - 1;
    printf("%d", r);
    return 0;
}

5555번: 반지

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


$O(n)$

#include<iostream>
#include<string>
using namespace std;
string p, q;
int n, r;
int main() {
    cin >> p >> n;
    while (n--) cin >> q, r += (q + q).find(p) != string::npos;
    cout << r;
    return 0;
}

2179번: 비슷한 단어

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


$O(nl\lg n)$

문자열을 사전순 정렬을 한 뒤에 인접한 문자열끼리 비교하면 각 문자열의 최대 공통접두사 길이를 구할 수 있다.
...
s1
s2
s3
...
sn
...
(s1, s2), (s2,s3), ..., (sn-1,sn) 공통접두사 길이가 같으면 s1~sn 중 먼저 입력받은 두 문자열을 고려한다.
공통접두사 길이가 최대값인 먼저 입력받은 두 문자열을 출력한다.

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s[20000];
pair<string, int> p[20000];
pair<int, int> r, t;
int n, maxi = -1, pre = -1, l;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)cin >> s[i], p[i] = { s[i],i };
    sort(p, p + n);
    unique(p, p + n);
    for (int i = 1; i < n; i++) {
        for (l = 0; l<p[i - 1].first.size() && l<p[i].first.size() && p[i - 1].first[l] == p[i].first[l]; l++);
        if (l^pre) pre = l, t = { p[i - 1].second,p[i].second };
        else if (t.second > p[i].second) t.second = p[i].second;
        if (t.first > t.second) swap(t.first, t.second);
        if (maxi < l || maxi == l&&r>t) maxi = l, r = t;
    }
    cout << s[r.first] + '\n' + s[r.second];
    return 0;
}

4354번: 문자열 제곱

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


$O(tl)$

failure function을 구현

#include<cstdio>
char s[1000001];
int f[1000001], i, j;
int main() {
    while (scanf("%s", s) && s[0] ^ '.') {
        for (f[i = 0] = j = -1; s[i]; ) j < 0 | s[j] == s[i] ? f[++i] = ++j : j = f[j];
        printf("%d\n", i % (i - f[i]) ? 1 : i / (i - f[i]));
    }
    return 0;
}

1032번: 명령 프롬프트

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


$O(nl)$

#include<cstdio>
int n;
char s[51], c;
int main() {
    scanf("%d %s", &n, s);
    for (int i = 1; i < n; i++) for (int j = 0; s[j]; j++) scanf(" %c", &c), s[j] = s[j] - c ? '?' : c;
    printf("%s", s);
    return 0;
}

10759번: 팰린드롬 경로 3

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

#include<stdio.h>
#define mod 1000000007
const int MAX_N = 500;
int n, dp[MAX_N][MAX_N];
char str[MAX_N][MAX_N + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", str[i]);
        dp[i][i] = 1;
    }
    for (int i = n - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            for (int k = 0; k <= i; k++)
                dp[j][k] = (str[i - j][j] == str[n - 1 - k][n - 1 - i + k])
                *((dp[j][k] + dp[j + 1][k + 1]) % mod + (dp[j + 1][k] + dp[j][k + 1]) % mod) % mod;
    printf("%d", dp[0][0]);
    return 0;
}

1958번: LCS 3

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


$O(lmn)$

2차원 lcs dp를 응용한다.

#include<cstdio>
#include<algorithm>
char s1[102], s2[102], s3[102];
int dp[101][101][101], i, j, k;
int main() {
    scanf("%s %s %s", s1 + 1, s2 + 1, s3 + 1);
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            for (k = 1; s3[k]; k++)
                dp[i][j][k] = std::max({ dp[i - 1][j - 1][k - 1] + (s1[i] == s2[j] && s1[i] == s3[k]),dp[i - 1][j][k],dp[i][j - 1][k],dp[i][j][k - 1] });
    printf("%d", dp[i - 1][j - 1][k - 1]);
    return 0;
}