Language: C++

#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

enum Type{
	Unknown,
	TRUE,
	FALSE,
};

struct Node{
	int parent_id,children[26],suffix_link;
	bool finish_FLG;
	string pattern;
};

struct Info{
	Info(string arg_parent,string arg_line){
		parent = arg_parent;
		line = arg_line;
	}

	string parent,line;
};

int index = 1,table[128];
char buf[NUM],P[NUM];
Node nodes[NUM];
Type memo[NUM];
map<string,int> MAP;


int main(){

	//ノードを数字化
	for(int i = 0; i < 26; i++){
		table['a'+i] = i;
	}

	scanf("%s",buf);
	int length;
	for(length = 0; buf[length] != '\0'; length++);

	//★ルートの情報を設定★
	int root = 0;
	nodes[root].pattern = "";

	//トライ木のノードを初期化
	for(int i = 0; i < NUM; i++){
		nodes[i].parent_id = -1;
		nodes[i].finish_FLG = false;
		nodes[i].suffix_link = root; //siffx_link先はとりあえずrootにしておく
		for(int k = 0; k < 26; k++){
			nodes[i].children[k] = -1;
		}
	}

	int N;
	scanf("%d",&N);


	int tmp_ch,tmp_loc,parent_id,tmp_index;
	string tmp_pattern;

	bool FLG;

	//トライ木を構成する
	for(int loop = 0; loop < N; loop++){

		scanf("%s",P);
		tmp_pattern.clear();

		tmp_index = 0;
		tmp_ch = table[P[tmp_index]];
		tmp_pattern += P[tmp_index];

		tmp_loc = root;
		tmp_index = 0;

		while(true){

			parent_id = tmp_loc;
			FLG = false;

			if(nodes[tmp_loc].children[tmp_ch] == -1){
				FLG = true;
				nodes[tmp_loc].children[tmp_ch] = index++; //★新しいノードへ移動する場合★
			}
			//子ノードに移動
			tmp_loc = nodes[tmp_loc].children[tmp_ch];

			if(FLG){
				nodes[tmp_loc].parent_id = parent_id;
				nodes[tmp_loc].pattern = tmp_pattern;

				//MAPに登録
				MAP[tmp_pattern] = tmp_loc;
			}

			tmp_index++;

			if(P[tmp_index] == '\0'){ //今回の数字が最後の文字だった場合
				nodes[tmp_loc].finish_FLG = true;
				break;
			}
			tmp_ch = table[P[tmp_index]];
			tmp_pattern += P[tmp_index];
		}
	}

	//Suffix_linkを構築する
	queue<Info> MAKE_SL;
	MAKE_SL.push(Info("",""));

	//1文字ずつ左に足していく
	while(!MAKE_SL.empty()){
		tmp_pattern = MAKE_SL.front();
		MAKE_SL.pop();

		for(int i = 0; i < 26; i++){
			string new_pattern = 'a'+i+tmp_pattern;

			auto at = MAP.find(new_pattern);
			if(at == MAP.end())continue;

			nodes[MAP[new_pattern]].suffix_link = MAP[tmp_pattern];
			MAKE_SL.push(Info(tmp_pattern,new_pattern));
		}
	}

	//suffix_linkを辿り、finish_flgがtrueのものに出くわすか調べる
	for(int i = 1; i < index; i++){
		memo[i] = Unknown;
	}


	queue<int> Q;
	for(int i = 0; i < 26; i++){
		if(nodes[root].children[i] != -1){
			Q.push(nodes[root].children[i]);
		}
	}

	//ノードに近いものから調べる
	while(!Q.empty()){
		tmp_loc = Q.front();
		Q.pop();
		for(int i = 0; i < 26; i++){
			if(nodes[tmp_loc].children[i] != -1){
				Q.push(nodes[tmp_loc].children[i]);
			}
		}

		if(nodes[tmp_loc].finish_FLG){
			memo[tmp_loc] = TRUE;
		}else{
			for(int k = nodes[tmp_loc].suffix_link; k != root; k = nodes[k].suffix_link){
				if(memo[k] != Unknown){
					memo[tmp_loc] = memo[k];
					break;
				}
				if(nodes[k].finish_FLG){
					memo[tmp_loc] = TRUE;
					break;
				}
			}
			if(memo[tmp_loc] == Unknown){
				memo[tmp_loc] = FALSE;
			}
		}
	}

	int ans = 0;
	tmp_loc = root;

	for(int i = 0; i < length; i++){
		tmp_ch = table[buf[i]];

		if(nodes[tmp_loc].children[tmp_ch] != -1){ //tmp_locから次に行ける場合
			tmp_loc = nodes[tmp_loc].children[tmp_ch];

			if(memo[tmp_loc] == TRUE){
				ans++;
				tmp_loc = root;
			}else{
				//Do nothing
			}

		}else{ //tmp_locから次へ行けない場合

			if(tmp_loc == root)continue; //rootの場合はSKIP

			//suffix_linkを辿り、tmp_chへ移れるノードがあるか調べる
			for(tmp_loc = nodes[tmp_loc].suffix_link; tmp_loc != root; tmp_loc = nodes[tmp_loc].suffix_link){
				if(nodes[tmp_loc].children[tmp_ch] != -1)break;
			}

			if(tmp_loc == root){ //rootまで戻った場合
				if(nodes[tmp_loc].children[tmp_ch] != -1){ //rootの子にtmp_chがいる場合
					tmp_loc = nodes[tmp_loc].children[tmp_ch];
					if(nodes[tmp_loc].finish_FLG){
						ans++;
						tmp_loc = root;
					}
				}else{
					//Do nothing
				}
			}else{ //途中でtmp_chへ移れるノードが見つかった場合
				tmp_loc = nodes[tmp_loc].children[tmp_ch];

				if(memo[tmp_loc] == TRUE){
						ans++;
						tmp_loc = root;
					}else{
						//Do nothing
					}
			}
		}
	}

	printf("%d\n",ans);

	return 0;
}



Compiler output:
a.cc:44:5: warning: built-in function 'index' declared as non-function [-Wbuiltin-declaration-mismatch]
   44 | int index = 1,table[128];
      |     ^~~~~
a.cc: In function 'int main()':
a.cc:135:45: error: no match for 'operator=' (operand types are 'std::string' {aka 'std::__cxx11::basic_string<char>'} and '__gnu_cxx::__alloc_traits<std::allocator<Info>, Info>::value_type' {aka 'Info'})
  135 |                 tmp_pattern = MAKE_SL.front();
      |                                             ^
In file included from /usr/include/c++/14/string:54,
                 from a.cc:8:
/usr/include/c++/14/bits/basic_string.h:941:8: note: candidate: 'template<class _Tp> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(const _Tp&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]'
  941 |        operator=(const _Tp& __svt)
      |        ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:941:8: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/14/bits/stl_pair.h:60,
                 from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/bits/specfun.h:43,
                 from /usr/include/c++/14/cmath:3906,
                 from a.cc:2:
/usr/include/c++/14/type_traits: In substitution of 'template<bool _Cond, class _Tp> using std::enable_if_t = typename std::enable_if::type [with bool _Cond = false; _Tp = std::__cxx11::basic_string<char>&]':
/usr/include/c++/14/bits/basic_string.h:149:8:   required by substitution of 'template<class _CharT, class _Traits, class _Alloc> template<class _Tp, class _Res> using std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv = std::enable_if_t<((bool)std::__and_<std::is_convertible<const _Tp&, std::basic_string_view<_CharT, _Traits> >, std::__not_<std::is_convertible<const _Tp*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>*> >, std::__not_<std::is_convertible<const _Tp&, const _CharT*> > >::value), _Res> [with _Tp = Info; _Res = std::__cxx11::basic_string<char>&; _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]'
  149 |         using _If_sv = enable_if_t<
      |               ^~~~~~
/usr/include/c++/14/bits/basic_string.h:941:8:   required by substitution of 'template<class _Tp> std::__cxx11::basic_string<char>::_If_sv<_Tp, std::__cxx11::basic_string<char>&> std::__cxx11::basic_string<char>::operator=(const _Tp&) [with _Tp = Info]'
  941 |        operator=(const _Tp& __svt)
      |        ^~~~~~~~
a.cc:135:31:   required from here
  135 |                 tmp_pattern = MAKE_SL.front();
      |                                             ^
/usr/include/c++/14/type_traits:2711:11: error: no type named 'type' in 'struct std::enable_if<false, std::__cxx11::basic_string<char>&>'
 2711 |     using enable_if_t = typename enable_if<_Cond, _Tp>::type;
      |           ^~~~~~~~~~~
/usr/include/c++/14/bits/basic_string.h:817:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]'
  817 |       operator=(const basic_string& __str)
      |       ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:817:37: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<Info>, Info>::value_type' {aka 'Info'} to 'const std::__cxx11::basic_string<char>&'
  817 |       operator=(const basic_string& __str)
      |                 ~~~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/14/bits/basic_string.h:828:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(const _CharT*) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]'
  828 |       operator=(const _CharT* __s)
      |       ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:828:31: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<Info>, Info>::value_type' {aka 'Info'} to 'const char*'
  828 |       operator=(const _CharT* __s)
      |                 ~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/basic_string.h:840:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(_CharT) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]'
  840 |       operator=(_CharT __c)
      |       ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:840:24: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<Info>, Info>::value_type' {aka 'Info'} to 'char'
  840 |       operator=(_CharT __c)
      |                 ~~~~~~~^~~
/usr/include/c++/14/bits/basic_string.h:858:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]'
  858 |       operator=(basic_string&& __str)
      |       ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:858:32: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<Info>, Info>::value_type' {aka 'Info'} to 'std::__cxx11::basic_string<char>&&'
  858 |       operator=(basic_string&& __str)
      |                 ~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/14/bits/basic_string.h:926:7: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>& std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator=(std::initializer_list<_Tp>) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]'
  926 |       operator=(initializer_list<_CharT> __l)
      |       ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:926:42: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<Info>, Info>::value_type' {aka 'Info'} to 'std::initializer_list<char>'
  926 |       operator=(initializer_list<_CharT> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
a.cc:139:51: error: no match for 'operator+' (operand types are 'int' and 'std::string' {aka 'std::__cxx11::basic_string<char>'})
  139 |                         string new_pattern = 'a'+i+tmp_pattern;
      |                                              ~~~~~^~~~~~~~~~~~
      |                                                 |  |
      |                                                 |  std::string {aka std::__cxx11::basic_string<char>}
      |                                                 int
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:627:5: note: candidate: 'template<class _Iterator> constexpr std::reverse_iterator<_Iterator> std::operator+(typename reverse_iterator<_Iterator>::difference_type, const reverse_iterator<_Iterator>&)'
  627 |     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:627:5: note:   template argument deduction/substitution failed:
a.cc:139:52: note:   'std::string' {aka 'std::__cxx11::basic_string<char>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  139 |                         string new_pattern = 'a'+i+tmp_pattern;
      |                                                    ^~~~~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1798:5: note: candidate: 'template<class _Iterator> constexpr std::move_iterator<_IteratorL> std::operator+(typename move_iterator<_IteratorL>::difference_type, const move_iterator<_IteratorL>&)'
 1798 |     operator+(typename move_iterator<_Iterator>::difference_type __n,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1798:5: note:   template argument deduction/substitution failed:
a.cc:139:52: note:   'std::string' {aka 'std::__cxx11::basic_string<char>'} is not derived from 'const std::move_iterator<_IteratorL>'
  139 |                         string new_pattern = 'a'+i+tmp_pattern;
      |                                                    ^~~~~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3598:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 3598 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3598:5: note:   template argument deduction/substitution failed:
a.cc:139:52: note:   mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
  139 |                         string new_pattern = 'a'+i+tmp_pattern;
      |                                                    ^~~~~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3616:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 3616 |     operator+(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3616:5: note:   template argument deduction/substitution failed:
a.cc:139:52: note:   mismatched types 'const _CharT*' and 'int'
  139 |                         string new_pattern = 'a'+i+tmp_pattern;
      |                                                    ^~~~~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3635:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 3635 |     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3635:5: note:   template argument ded