fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define true 1
  5. #define false 0
  6.  
  7. struct node_st{
  8. 	char c;
  9. 	struct node_st *next;
  10. 	struct node_st *prev;
  11. 	struct node_st *jump;
  12. }typedef node_st;
  13.  
  14. struct head_st{
  15. 	node_st *first;
  16. 	node_st *last;
  17. }typedef head_st;
  18.  
  19. void Add(char c, head_st *h);
  20. void SetJump(head_st *h);
  21. int Check(head_st *h, char *S);
  22. void FreeH(head_st *h);
  23.  
  24. int main(void){
  25. 	int T;
  26. 	char *L, *S;
  27. 	head_st *head;
  28.  
  29. 	head = (head_st*)malloc(sizeof(head_st));
  30.  
  31. 	scanf("%d", &T);
  32. 	for(int j=0; j<T; j++){
  33. 		head->first=NULL, head->last=NULL;
  34.  
  35. 		scanf("%ms", &L);
  36. 		scanf("%ms", &S);
  37.  
  38. 		for(int i=0; L[i] != '\0'; i++){
  39. 			Add(L[i], head);
  40. 		}
  41.  
  42. 		SetJump(head);
  43.  
  44. 		if(Check(head,S) == true)
  45. 			printf("Yes\n");
  46. 		else
  47. 			printf("No\n");
  48.  
  49. 		FreeH(head);
  50. 		free(S);
  51. 		free(L);
  52. 	}
  53.  
  54. 	free(head);
  55.  
  56. 	return 0;
  57. }
  58.  
  59. void Add(char c, head_st *h){
  60. 	node_st *node, *aux;
  61.  
  62. 	//remover ? e * desnecessarios
  63. 	if(h->last != NULL){
  64. 		if(c == '?' && h->last->c == '*')
  65. 			return;
  66. 		else if(c == '*'){
  67. 			aux = h->last;
  68. 			while(aux != NULL && (aux->c == '?' || aux->c == '*'))
  69. 				aux = aux->prev;
  70. 			h->last=aux;
  71.  
  72. 			if(aux == NULL)
  73. 				h->first = NULL;
  74. 		}
  75. 	}
  76.  
  77. 	node = (node_st*)malloc(sizeof(node_st));
  78.  
  79. 	node->c = c;
  80. 	node->jump = NULL;
  81. 	node->next = NULL;
  82. 	node->prev = h->last;
  83.  
  84. 	if(h->first != NULL)
  85. 	       	h->last->next = node;
  86. 	else
  87. 		h->first = node;
  88.  
  89. 	h->last = node;
  90. }
  91.  
  92. void SetJump(head_st *h){
  93. 	node_st *node, *jmp=NULL;
  94. 	char c='-';
  95.  
  96. 	node = h->last;
  97.  
  98. 	while(node != NULL){
  99. 		if(node->c == '*' || node->c == '?')
  100. 			node->jump = jmp;
  101. 		else
  102. 			jmp = node;
  103.  
  104. 		node = node->prev;
  105. 	}
  106. }
  107.  
  108. int Check(head_st *h, char *S){
  109. 	node_st *node, *nodeRet;
  110. 	int i=0, indRet;
  111.  
  112. 	nodeRet = NULL;
  113. 	node = h->first;
  114.  
  115. 	while(node != NULL && S[i] != '\0'){
  116. 		//printf("1 - L: %c | S: %c\n",node->c,S[i]);
  117. 		if(node->c == '?'){
  118. 			if(node->jump != NULL && S[i] == node->jump->c){
  119. 				nodeRet = node->next;
  120. 				indRet = ++i;
  121. 				node = node->jump->next;
  122. 			}
  123. 			else{
  124. 				node = node->next;
  125. 				i++;
  126. 			}
  127.  
  128. 		}
  129. 		else if(node->c == '*'){
  130. 			nodeRet = node;
  131. 			if(node->next == NULL){
  132. 				return true;
  133. 			}
  134. 			else if(node->jump != NULL && S[i] == node->jump->c){
  135. 				node = node->jump->next;
  136. 			}
  137. 			else{
  138. 				node = node->next;
  139. 			}
  140. 			indRet = ++i;
  141. 		}
  142. 		else{
  143. 			if(node->c != S[i])
  144. 				if(nodeRet == NULL)
  145. 					return false;
  146. 				else{
  147. 					node = nodeRet;
  148. 					i = indRet;
  149. 					nodeRet = NULL;
  150. 				}
  151. 			else{
  152. 				node = node->next;
  153. 				i++;
  154. 			}
  155. 		}
  156.  
  157. 		if(node == NULL && S[i] != '\0'){
  158. 			if(nodeRet == NULL)
  159. 				return false;
  160. 			else{
  161. 				node = nodeRet;
  162. 				i = indRet;
  163. 				nodeRet = NULL;
  164. 			}
  165. 		}
  166. 	}
  167.  
  168. 	while(node != NULL && (node->c == '*' || node->c == '?'))
  169. 		node = node->next;
  170.  
  171. 	if(node == NULL && S[i] == '\0') return true;
  172. 	else return false;
  173. }
  174.  
  175. void FreeH(head_st *h){
  176. 	node_st *aux, *aux2;
  177.  
  178. 	aux = h->first;
  179. 	while(aux!=NULL){
  180. 		aux2=aux->next;
  181. 		free(aux);
  182. 		aux=aux2;
  183. 	}
  184.  
  185. }
  186.  
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OoRfDB
problem AUTOMATA, based on SPOJ submission 23655429 (C), 2019-04-19 05:15:51
language:
C (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!