문자열 접두사-접미사 매칭 문제 개요

여러 문자열의 접두사와 접미사를 매칭하는 문제는 일반적으로 전처리 과정을 통해 해결한다.
고정된 단어 개수를 가진 문자열 배열 s[n]이 주어졌을 때, 각 문자열을 cin으로 입력받아 처리한다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // 여러 문자열 매칭을 위한 전처리 연산
    }
}

답을 구할 때는 새로 생성된 string의 크기에서 최댓값을 취하며, int 변환이 필요하다.
ans = max(ans, (int)string.size());

KMP 알고리즘 구현

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    // ne[j]는 길이가 j인 문자열의 접두사와 접미사가 일치하는 최대 길이를 저장
    // j 자체는 길이를 의미하며, j+1은 비교할 현재 인덱스를 나타냄
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}

특정 문자 조건을 만족하는 부분 문자열 개수 세기

'P' 문자를 만나면 문자열을 분할하고, 각 분할된 문자열에서 k개 이상의 'R'을 포함하는 부분 문자열 개수를 센다.
고정된 오른쪽 끝점에서 왼쪽 끝점을 이동시키며 조건을 만족하는 경우를 카운트한다.

#include<bits/stdc++.h>
using namespace std;
int n,k;
string s;
long long res=0;

void gao(string t){
    int i,j=0,temp=0;
    for(i=0;i<t.length();i++){
        temp+=t[i]=='R';
        while(j<=i&&temp==k){
            temp-=t[j++]=='R';
        }
        res+=j;
    }
}

int main(){
    int i;
    cin>>n>>k>>s;
    string t="";
    for(i=0;i<n;i++){
        if(s[i]=='P') gao(t), t="";
        else t+=s[i];
    }
    gao(t);
    cout<<res;
}

0부터 시작하는 KMP 구현 (j=-1 초기화 불필요)

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int ne[N];
int n, m;
string p, s;

int main(){
    cin >> n >> p >> m >> s;

    for(int i = 1, j = 0; i < n; i++){
        while(j && p[i] != p[j]) j = ne[j - 1];
        if(p[i] == p[j]) j++;
        ne[i] = j;
    }

    for(int i = 0, j = 0; i < m; i++){
        while(j && s[i] != p[j]) j = ne[j - 1];
        if(s[i] == p[j]){
            j++;
            if(j == n){
                cout << i - n + 1 << " ";
                j = ne[n - 1];
            }
        }
    }
    return 0;
}

트라이(Trie) 자료구조

트라이의 핵심은 idx 변수를 활용한 노드 관리이다.

#include <iostream>
using namespace std;

const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str){
    int p = 0;
    for (int i = 0; str[i]; i++){
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(char *str){
    int p = 0;
    for (int i = 0; str[i]; i++){
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main(){
    int n;
    scanf("%d", &n);
    while (n--){
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}

최대 XOR 쌍 찾기

각 숫자에 대해 최상위 비트부터 저장하여, 반대 비트를 가진 숫자를 찾아 XOR 값이 최대가 되도록 한다.

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010, M = 3100010;
int n;
int a[N], son[M][2], idx;

void insert(int x){
    int p = 0;
    for (int i = 30; i >= 0; i--){
        int &s = son[p][x >> i & 1];
        if (!s) s = ++idx;
        p = s;
    }
}

int search(int x){
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--){
        int s = x >> i & 1;
        if (son[p][!s]){
            res += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, search(a[i]));
    printf("%d\n", res);
    return 0;
}

순열 사이클 찾기 (교환 병 문제)

int main(){
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        if(!st[i]){
            for (int j = i; !st[j]; j=a[j]){
                st[j]=true;
            }
            cnt++;
        }
    }
    cout<<n-cnt<<endl;
    return 0;
}

부분 문자열 등장 횟수 (접두사 합 활용)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;
int n, m, Q;
string S, T;
int s[N];

int main(){
    scanf("%d%d%d", &n, &m, &Q);
    char strs[N], strt[N];
    scanf("%s%s", strs, strt);
    S = strs, T = strt;
    S = ' ' + S;

    for (int i = m; i <= n; i++){
        s[i] = s[i-1];
        if (S.substr(i - (m-1), m) == T)
            s[i]++;
    }

    while (Q--){
        int l, r;
        scanf("%d%d", &l, &r);
        l += (m - 1);
        if (l > r) puts("0");
        else printf("%d\n", s[r] - s[l-1]);
    }
    return 0;
}

양방향 BFS를 활용한 문자열 변환

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;

const int N = 6;
int n;
string A,B;
string a[N], b[N];
queue<string> qa, qb;
unordered_map<string,int> da, db;

int extend(queue<string>& q, unordered_map<string,int>& da, unordered_map<string,int>& db, string a[], string b[]){
    int d = da[q.front()];
    while(q.size() && da[q.front()] == d){
        auto t = q.front();
        q.pop();
        for (int i = 0; i < n; i++){
            for (int j = 0; j < t.size(); j++){
                if(t.substr(j, a[i].size()) == a[i]){
                    string r = t.substr(0,j) + b[i] + t.substr(j + a[i].size());
                    if(db.count(r)) return da[t] + db[r] + 1;
                    if(da.count(r)) continue;
                    q.push(r);
                    da[r] = da[t] + 1;
                }
            }
        }
    }
    return 11;
}

int bfs(){
    if(A == B) return 0;
    qa.push(A); qb.push(B);
    da[A] = 0; db[B] = 0;
    int step = 0;
    while(qa.size() && qb.size()){
        int t;
        if(qa.size() < qb.size()) t = extend(qa, da, db, a, b);
        else t = extend(qb, db, da, b, a);
        if(t <= 10) return t;
        if(++step == 10) return -1;
    }
    return -1;
}

int main(){
    cin >> A >> B;
    while(cin >> a[n] >> b[n]) n++;
    int t = bfs();
    if(t == -1) cout << "NO ANSWER!" << endl;
    else cout << t << endl;
    return 0;
}

단어 사슬 (Word Chain)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 21;

int n, m;
string word[N];
int ans;
int used[N];
int g[N][N];

void dfs(string dragon, int last){
    ans = max((int)dragon.size(), ans);
    used[last]++;
    for(int i = 0; i < n; i++){
        if(g[last][i] && used[i] < 2){
            dfs(dragon + word[i].substr(g[last][i]), i);
        }
    }
    used[last]--;
}

int main(){
    cin >> n;
    char start;
    for (int i = 0; i < n; i++) cin >> word[i];
    cin >> start;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = 1; k < min(word[i].size(), word[j].size()); k++)
                if(word[i].substr(word[i].size()-k, k) == word[j].substr(0, k)){
                    g[i][j] = k;
                    break;
                }
        }
    }
    for (int i = 0; i < n; i++){
        if(word[i][0] == start)
            dfs(word[i], i);
    }
    cout << ans;
    return 0;
}

십이지년도 차이 계산

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;

unordered_map<string, int> zodiac = {
    {"Ox", 0}, {"Tiger", 1}, {"Rabbit", 2},
    {"Dragon", 3}, {"Snake", 4}, {"Horse", 5},
    {"Goat", 6}, {"Monkey", 7}, {"Rooster", 8},
    {"Dog", 9}, {"Pig", 10}, {"Rat", 11}
};

int main(){
    unordered_map<string, int> offset;
    offset["Bessie"] = 0;
    int n;
    cin >> n;
    while (n--){
        string s[8];
        for (int i = 0; i < 8; i++) cin >> s[i];
        if (s[3] == "previous"){
            int x = offset[s[7]], y = zodiac[s[4]];
            int r = ((x - y) % 12 + 12) % 12;
            if (!r) r = 12;
            offset[s[0]] = x - r;
        }
        else {
            int x = offset[s[7]], y = zodiac[s[4]];
            int r = ((y - x) % 12 + 12) % 12;
            if (!r) r = 12;
            offset[s[0]] = x + r;
        }
    }
    cout << abs(offset["Elsie"]) << endl;
    return 0;
}