fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. /**
  6.  * Note: The returned array must be malloced, assume caller calls free().
  7.  */
  8. struct pair{
  9.     int word;
  10.     int indexInS;
  11. };
  12.  
  13. int cmp(const void* a, const void* b) {
  14.     return (((struct pair*)a)->indexInS - ((struct pair*)b)->indexInS);
  15. }
  16. // find substring such that the return index % n == 0
  17. char* findSubstringAtN(char* s, char* word, int n) {
  18.     int i;
  19.     while (1) {
  20.         i = 0;
  21.         for (i = 0; i < n; ++i)
  22.             if (s[i] != word[i]) break;
  23.         if (i == n) return s;
  24.         // not found
  25.         s+=i;
  26.         while (*s != '\0' && i < n) {
  27.             ++s;
  28.             ++i;
  29.         }
  30.         if (i != n) return NULL;
  31.     }
  32. }
  33.  
  34. int* findSubstring(char* s, char** words, int wordsSize, int* returnSize) {
  35.     int wordLen = strlen(words[0]);
  36.     int* ans = (int*)malloc(sizeof(int) * strlen(s));
  37.     *returnSize = 0;
  38.     printf("%c ", s[0]);
  39.  
  40.     int i, j, k, continue_flag;
  41.     char* ptr;
  42.  
  43.     struct pair index[wordsSize], temp;
  44.     for (i = 0; i < wordLen; ++i) {
  45.         //if (start[i] == 0) continue;
  46.         char* s1 = s + i;
  47.         int skip = 0;
  48.  
  49.         for (j = 0; j < wordsSize  && s+i != '\0'; ++j) {
  50.             ptr = findSubstringAtN(s1+skip, words[j], wordLen);
  51.             printf("%d %d %p ", i, j, ptr);
  52.             if (ptr) {
  53.                 index[j].word = j;
  54.                 index[j].indexInS = ptr - s1;
  55.                 if (index[j].indexInS == skip) skip += wordLen;
  56.             }
  57.             else break;
  58.         }
  59.         if (ptr == NULL) continue;
  60.         while (1) {
  61.             continue_flag = 0;
  62.             qsort(index, wordsSize, sizeof(struct pair), cmp);
  63.             for (j = 0; j < wordsSize - 1; ++j) {
  64.             	for (k = 0; k < wordsSize; ++k)
  65.             		printf("%d ", index[k].indexInS);
  66.             	printf("\n");
  67.                 // words = ["aa","aa", ...]
  68.                 if (index[j].indexInS == index[j + 1].indexInS) {
  69.                 	printf("1:%d\n", j);
  70.                     ptr = findSubstringAtN(s1+index[j].indexInS+wordLen, words[index[j].word], wordLen);
  71.                     if (ptr) {
  72.                         index[j+1].indexInS = ptr - s1;
  73.                         temp = index[j + 1];
  74.                         for (k = j+2; k<wordsSize; ++k) {
  75.                             if (index[k].indexInS < temp.indexInS)
  76.                                 index[k-1] = index[k];
  77.                             else break;
  78.                         }
  79.                         index[k-1] = temp;
  80.                         //qsort(index, wordsSize, sizeof(struct pair), cmp);
  81.                         --j;
  82.                         continue;
  83.                     }
  84.                     else break;
  85.                 }
  86.  
  87.                 if (index[j].indexInS + wordLen != index[j + 1].indexInS) {
  88.                 	printf("2:%d\n", j);
  89.                     ptr = findSubstringAtN(s1+index[0].indexInS+wordLen, words[index[0].word], wordLen);
  90.                     if (ptr) {
  91.                         index[0].indexInS = ptr - s1;
  92.                         temp = index[0];
  93.                         for (k = 1; k<wordsSize; ++k) {
  94.                             if (index[k].indexInS < temp.indexInS)
  95.                                 index[k-1] = index[k];
  96.                             else break;
  97.                         }
  98.                         index[k-1] = temp;
  99.                         if (j == 0) --j;
  100.                         else j -= 2;
  101.                         continue;
  102.                     }
  103.                     break;
  104.                 }
  105.             }
  106.             if (ptr == NULL) break;
  107.             //if (continue_flag == 1) continue;
  108.             printf("out\n");
  109.             ans[*returnSize] = index[0].indexInS + i;
  110.             (*returnSize)++;
  111.             // find next concatenated string
  112.             ptr = findSubstringAtN(s1+index[wordsSize-1].indexInS+wordLen, words[index[0].word], wordLen);
  113.             if (ptr) index[0].indexInS = ptr - s1;
  114.             else break; // no more concatenated string
  115.         }
  116.     }
  117.     return ans;
  118. }
  119.  
  120.  
  121. int main(void) {
  122. 	// your code goes here
  123. 	//char s[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
  124. 	char s[] = "b";
  125. 	char* words[5000];
  126. 	//for (int i = 0; i < 5000; ++i)
  127. 	//	words[i] = "a";
  128. 	words[0] = "bbb";
  129. 	words[1] = "bbb";
  130. 	words[2] = "a";
  131. 	words[3] = "c";
  132. 	words[4] = "a";
  133. 	words[5] = "a";
  134. 	words[6] = "a";
  135. 	words[7] = "b";
  136. 	words[8] = "c";
  137.  
  138. 	int returnSize;
  139. 	int*a = findSubstring(s, words, 2, &returnSize);
  140. 	printf("output:");
  141. 	for (int i = 0; i < returnSize; ++i)
  142. 		printf("%d ", a[i]);
  143. 	return 0;
  144. }
  145.  
Compilation #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/iGGPLq
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C (gcc 8.3)

					

					

						
created:
								
						
11 days 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!