KMP

긴 문자열에서 특정 단어를 찾을때 사용하는 알고리즘이다. 

 

원래의 시간 복잡도는 특정단어 * 긴문자열 이라는 시간이 나오는데  이것을 줄인 것이다. 

 

알고리즘 이해가 좀 어렵다. 모르면 꼭 다른곳을 찾아봐서 복습하자

 

 

string 은 char[100000] 으로 해서 풀어도 된다. 설마 여기까지 왔는데 이걸 변환 못하는건 말이 안되지 않을까?

#include <iostream>
#include <string>
#define pii pair<int, int>
using namespace std;
 
int p_fail[1000000] = { 0 }; 
int ans[1000000];
int siz= 0;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    string t, p;
 
    getline(cin, t);
    getline(cin, p);
 
    /* 
    
       fail  함수를 구해보자.
       p_fail 함수는 문자열 p의 처음 글자중 일치하는 접두사의 최대 길이이다.
                     그리고 p_fail[i] 는 일치하는 접두사들의 다음 문자이다.
 
       abcabcabca 의 fail 함수는??? -> 0 0 0 1 2 3 4 5 6 7
       
       abacabad 의 fail 함수는 ??? -> 0 0 1 0 1 2 3 0
 
       while(base > 0 && p[i] != p[base]) 가 정말 제일 중요하다.
       abacabad 에서 i가 7일때를 보자. (그러면 base는 3부터 시작한다.)
 
       p[7] 와 p[3] 을 비교해서 다르니깐  base는 p_fail[3-1] => 1이다.
       p[7] 와 p[1] 을 비교해서 다르니깐 base는 p_fail[1-1] -> 0 이다.
       0 이면 break 고
       p[i] == p[base]도 false니깐 0이된다.
 
 
    */
    int base = 0;
    for (int i = 1; i < p.size(); i++)
    {
        while (base > 0 && p[i] != p[base])
            base = p_fail[base - 1];
 
        if (p[i] == p[base])
            p_fail[i] = ++base;
 
    }
 
 
    base = 0;
 
    /* 
    abcabcabcabcabcabcabcabca
    abcabca 를 기준으로 해보자. fail 함수는 0 0 0 1 2 3 4
 
    while (base > 0 && t[i] != p[base]) 은 fail 함수와 비슷하고
 
    i가 6인 상태에서 t[i] == p[base] 이고 base == 6 == p_size-1 이니깐 
 
    base = p_fail[base] 이다. p_fail[6] = 4 니깐 
 
    문자를 완전히 찾았을때 base값은 겹치는 문자열들의 다음값으로 잡아주는 것이다.
 
 
 
 
    */
    for (int i = 0; i < t.size(); i++)
    {
        while (base > 0 && t[i] != p[base])
            base = p_fail[base - 1];
 
        if (t[i] == p[base])
        {
            if (base == p.size() - 1)
            {
                ans[siz++] = i - base + 1;
                base = p_fail[base];
            }
            else
            {
                base++;
            }
            
        }
    }
 
    cout << siz << '\n';
    for (int i = 0; i < siz; i++)
        cout << ans[i] << ' ';
 
 
}