백준(BOJ) 1097 마법단어 **

# kmp

우선 문제 지문 읽기가 헬오브 헬...

간단하게 생각하면 1~n까지의 문자열의 순열(T(0))이 i번째 부터 시작했을때 T(0)과 같은 갯수가 k개인 경우를 세주는 거다.

ex) n=3, AB,RAAB,RA 문자열 주어진 경우 

ABRAABRA

ABRARAAB

RAABABRA

RAABRAAB

RAABRAAB

RARAABAB

다음과 같이 6개의 경우가 나오게 된다.

여기서 하나의 순열(ABRAABRA)을 보게된다면.

ABRAABRAABRAABRA

ABRAABRA                  

ABRAABRA

총 i가 2가 되고, i==k 이기 떄문에 마법의 단어가 된다.

이런 순열이 총 3개가 된다.

 

문자열 순열에는 몇가지 규칙이있다.

1234, 2341, 3412, 4123 이렇게 돌려서 동일한 순열이 되는경우 동일한 i개를 가지게 된다.

(즉, 하나의 순열에 대해서만 kmp를 시행하면된다.)

돌려서 동일하지 않은 순열에 대해서 kmp를 돌리면된다.

돌려서 동일하지 않은 순열을 만들기 위해서는 맨앞을 1로 기준을 잡고 순열을 만들면 된다.

ex) n=4 1,2,3,4

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

 

# 실수 했던 점

kmp에서 smp.size()-1까지 반복시켜야한다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 205
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int n,m,ans=0,mem[MAX];
char str[15][25];
bool tf[10];
vector<int>v;
vector<string> vs;

int kmp(int in)
{
    int ret=0;
    string smp=vs[in],pat=vs[in];
    smp.append(vs[in]);
    // 비교될 문자열(smp) = 만들어진 문자열*2를 한다.
    // 비교할 문자열(pat) = 만들어진 문자열
    
    int j = 0;
    for (int i = 0; i < smp.size()-1; i++)
    {
        while (j > 0 && smp.at(i) != pat.at(j))
            j = mem[j - 1];
        if (smp.at(i) == pat.at(j))
        {
            if (j == pat.size() - 1)
            {
                ret++;
                j=mem[j];
            }
            else
                j++;
        }
    }
    return ret;
}

void getpi(int in)
//pi값을 생성한다.
{
    int j = 0;
    for (int i = 1; i < vs[in].size(); i++)
    {
        while (j > 0 && vs[in].at(i) != vs[in].at(j))
            j = mem[j - 1];
        if (vs[in].at(i) == vs[in].at(j))
            mem[i] = ++j;
    }
    return ;
}

void make_string()
// 최초 문자열로 문자열을 만들어준다.
{
    if(v.size()==n)
    {
        string tmp;
        for(int i=0;i<v.size();i++)
            tmp.append(str[v[i]]);
        vs.push_back(tmp);
        return ;
    }
    for(int i=2;i<=n;i++)
        if(!tf[i])
        {
            tf[i]=true;
            v.push_back(i);
            make_string();
            v.pop_back();
            tf[i]=false;
        }
}

int main()
{
    scanf("%d",&n);
    v.push_back(1);
    for(int i=1;i<=n;i++)
        scanf("%s",str[i]);
    // 문자열 입력으로 받아오고
    make_string();
    // 문자열 조합으로 만들어준다.
    scanf("%d",&m);
    for(int i=0;i<vs.size();i++)
    {
        getpi(i);
        if(kmp(i)==m)
            ans+=n;
    }
    // 각각 kmp돌려준다.
    printf("%d",ans);
    return 0;
}