백준(BOJ) 16172 나는 친구가 적다 **

# kmp

단순한 kmpㅎㅎ

#include<iostream>
#include<cstdio>
#include<vector>
#include <deque>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 1000005

char a[MAX], b[MAX], c[MAX];
int p[MAX];

int main()
{
	scanf("%s", a);
	scanf("%s", c);
	int idx = 0;
	for (int i = 0; i < strlen(a); i++)
	{
		if ('0' <= a[i] && a[i] <= '9')
			continue;
		else
		{
			b[idx] = a[i];
			idx++;
		}
	}

	// Make Pi array.
	int j = 0;
	for (int i = 1; i < strlen(c); i++) 
	{
		while (j > 0 && c[i] != c[j]) {
			j = p[j - 1];
		}
		if (c[i] == c[j])
			p[i] = ++j;
	}

	// Using KMP
	j = 0;
	vector<int> ans;
	for (int i = 0; i < idx; i++) {
		while (j > 0 && b[i] != c[j]) {
			j = p[j - 1];
		}
		if (b[i] == c[j]) {
			if (j == strlen(c) - 1) {
				printf("1");
				return 0;
			}
			else {
				j++;
			}
		}
	}
	printf("0");
	return 0;
}