---
tags: codebook
---

{%hackmd theme-dark %}

# suffix trie

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
constexpr size_t cAlphaSize = 128;
struct suffix_trie {
	struct node {
		size_t start, end, index;
		node *slink;
		vector<node*> next;
	}*root, *needslink, *active_node;
	string data;
	size_t remainder, active_index, active_length;
	size_t length(node* x) {
		return min(x->end, data.size()) - x->start;
	}
	node* newnode(size_t a, size_t b = string::npos, size_t c = 0) {
		node* x = new node;
		x->start = a, x->end = b;
		x->index = c ? c : data.size() - remainder;
		x->next.assign(cAlphaSize, x->slink = root);
		return x;
	}
	size_t active_edge() {return data[active_index];}
	void addslink(node* x) {
		if (needslink != root)
			needslink->slink = x;
		needslink = x;
	}
	bool walk_down(node* x) {
		if (active_length < length(x))
			return false;
		active_index += length(x);
		active_length -= length(x);
		active_node = x;
		return true;
	}
	void init() {
		active_node = needslink = root = newnode(string::npos, string::npos);
		active_index = active_length = remainder = 0;
		root->next.assign(cAlphaSize, root->slink = root);
	}
	void extend(char c) {
		data.push_back(c);
		needslink = root, remainder++;
		while (remainder > 0) {
			if (!active_length)
				active_index = data.size() - 1;
			if (active_node->next[active_edge()] == root)
				active_node->next[active_edge()] = newnode(data.size() - 1), addslink(active_node);
			else {
				node* nxt = active_node->next[active_edge()];
				if (walk_down(nxt)) continue;
				if (data[nxt->start + active_length] == c) {
					active_length++;
					addslink(active_node);
					break;
				}
				node* split = newnode(nxt->start, nxt->start + active_length, string::npos);
				active_node->next[active_edge()] = split;
				split->next[size_t(c)] = newnode(data.size() - 1);
				nxt->start += active_length;
				split->next[size_t(data[nxt->start])] = nxt;
				addslink(split);
			}
			remainder--;
			if (active_node == root && active_length)
				active_length--, active_index = data.size() - remainder;
			else
				active_node = active_node->slink;
		}
	}
	void dfs(node* cur, vector<size_t>& v) {
		if (cur == root) return;
		if (cur->index != string::npos)
			v.push_back(cur->index);
		for (size_t i = 0; i != cAlphaSize; i++)
			dfs(cur->next[i], v);
	}
	vector<size_t> search(const string& str) {
		vector<size_t> v;
		node* cur = root->next[str.front()];
		size_t i = 0, j = 0;
		while (cur != root && i < str.size()) {
			if (j >= length(cur))
				cur = cur->next[str[i]], j = 0;
			if (str[i] != data[cur->start + j])
				return v;
			i++, j++;
		}
		if (cur != root)
			dfs(cur, v);
		return v;
	}
	bool count(const string& str) {
		node* cur = root->next[str.front()];
		size_t i = 0, j = 0;
		while (cur != root && i < str.size()) {
			if (j >= length(cur))
				cur = cur->next[str[i]], j = 0;
			if (str[i] != data[cur->start + j])
				return false;
			i++, j++;
		}
		return cur != root;
	}
	suffix_trie(const string & str) {
		init();
		for (const auto& i : str)
			extend(i);
		extend('\0');
	}
};
ostream& operator<<(ostream& os, const vector<auto>& v) {
	for (const auto& i : v)
		os << i << ' ';
	return os;
}
int main() {
	string a, b;
	while (cin >> a >> b)
		cout << vector<string> {"No", "Yes"} [suffix_trie(b).count(a)] << endl;
	return 0;
}