Skip to content

Instantly share code, notes, and snippets.

@kgashok

kgashok/replace.html

Last active June 4, 2018 21:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kgashok/6a9beb95e0c97d6eb0ea46ecb6ba4295 to your computer and use it in GitHub Desktop.
Save kgashok/6a9beb95e0c97d6eb0ea46ecb6ba4295 to your computer and use it in GitHub Desktop.
Download ZIP
replaceString
Raw
replace.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>replaceRefactorSaga</title>
<link rel="stylesheet" href="https://stackedit.io/style.css" />
</head>
<body class="stackedit">
<div class="stackedit__left">
<div class="stackedit__toc">
<ul>
<li><a href="#refactor-3">Refactor 3</a></li>
<li><a href="#refactor-2">Refactor 2</a></li>
<li><a href="#refactor-1">Refactor 1</a></li>
<li><a href="#original-sin">Original Sin</a></li>
</ul>
</div>
</div>
<div class="stackedit__right">
<div class="stackedit__html">
<h1 id="refactor-3">Refactor 3</h1>
<p>Instead of</p>
<pre class=" language-c"><code class="prism language-c"><span class="token keyword">char</span><span class="token operator">*</span> result <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token punctuation">)</span> <span class="token function">malloc</span><span class="token punctuation">(</span>sTarget <span class="token operator">*</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre>
<p>we will use <code>calloc</code> to initialize <code>'\0'</code> in all the memory locations that was alloted, as follows:</p>
<pre class=" language-c"><code class="prism language-c"><span class="token keyword">char</span> <span class="token operator">*</span>result <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token punctuation">)</span> <span class="token function">calloc</span><span class="token punctuation">(</span>sTarget<span class="token punctuation">,</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre>
<p>This ensures that valid NTBS strings are available to <code>strncat</code> inside the <code>for</code> loop (look up this SO answer - <a href="http://j.mp/valgrindErrorStrcat">http://j.mp/valgrindErrorStrcat</a> )</p>
<h1 id="refactor-2">Refactor 2</h1>
<pre class=" language-c"><code class="prism language-c"><span class="token keyword">int</span> <span class="token function">populate</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> target<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> find<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>findmap<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">do</span> <span class="token punctuation">{</span>
findmap<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">strstr</span><span class="token punctuation">(</span>target<span class="token punctuation">,</span> find<span class="token punctuation">)</span><span class="token punctuation">;</span>
target <span class="token operator">=</span> findmap<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span> <span class="token keyword">while</span> <span class="token punctuation">(</span>target<span class="token operator">++</span> <span class="token operator">&amp;&amp;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> i<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token comment">// The algorithm used is a 3 step process - first, find</span>
<span class="token comment">// all the matches, then allocate sufficient memory and then </span>
<span class="token comment">// do the actual concatenation of strings</span>
<span class="token keyword">char</span><span class="token operator">*</span> <span class="token function">replaceString</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> target<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> find<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> replace<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token comment">// STEP 1: Find all the pointers where there is a substring</span>
<span class="token comment">// match with 'find'</span>
<span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>matchMap<span class="token punctuation">[</span><span class="token number">20</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token function">populate</span><span class="token punctuation">(</span>target<span class="token punctuation">,</span> find<span class="token punctuation">,</span> matchMap<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">"count: %d\n"</span><span class="token punctuation">,</span> count<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">// STEP 2: Allocate enough memory to build the new string</span>
<span class="token keyword">int</span> sTarget <span class="token operator">=</span> <span class="token function">strlen</span><span class="token punctuation">(</span>target<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>replace<span class="token punctuation">)</span> <span class="token operator">*</span> count<span class="token punctuation">;</span> <span class="token comment">// abundantly sufficient</span>
<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">"Final size: %d\n"</span><span class="token punctuation">,</span> sTarget<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">char</span><span class="token operator">*</span> result <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">char</span><span class="token operator">*</span><span class="token punctuation">)</span> <span class="token function">malloc</span> <span class="token punctuation">(</span>sTarget <span class="token operator">*</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">char</span><span class="token operator">*</span> rp <span class="token operator">=</span> result<span class="token punctuation">;</span>
<span class="token keyword">int</span> i<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>prev <span class="token operator">=</span> target<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>index<span class="token punctuation">;</span>
<span class="token comment">// STEP 3: Build the string by processing each pointer where</span>
<span class="token comment">// a match was found. First, transfer the portion of string </span>
<span class="token comment">// until the match, concatenate the 'find' string and repeat</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> count<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
index <span class="token operator">=</span> matchMap<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// the index where a match was found</span>
<span class="token function">strncat</span><span class="token punctuation">(</span>rp<span class="token punctuation">,</span> prev<span class="token punctuation">,</span> index <span class="token operator">-</span> prev<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">strcat</span><span class="token punctuation">(</span>rp<span class="token punctuation">,</span> replace<span class="token punctuation">)</span><span class="token punctuation">;</span>
rp <span class="token operator">=</span> result <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>result<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// move rp to the end</span>
prev <span class="token operator">=</span> index <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>find<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// move prev beyond 'find' string</span>
<span class="token punctuation">}</span>
<span class="token comment">// the last bit from `target` string is required</span>
<span class="token function">strcat</span><span class="token punctuation">(</span>rp<span class="token punctuation">,</span> prev<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
<p>The key line of code is <strong>strncat (rp, prev, prev - index)</strong></p>
<ul>
<li><strong>rp</strong> is a pointer where the ‘resultant’ string needs to be updated,</li>
<li><strong>prev</strong> is a pointer to the location just past the last occurrence of ‘find’</li>
<li><strong>index</strong> is a pointer to the current occurrence of ‘find’</li>
<li><strong>prev - index</strong> is the pointer arithmetic provides the count of characters to copy</li>
</ul>
<hr>
<h1 id="refactor-1">Refactor 1</h1>
<pre class=" language-c"><code class="prism language-c">
<span class="token keyword">int</span> <span class="token function">populate</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> target<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> find<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>findmap<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">do</span> <span class="token punctuation">{</span>
findmap<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">strstr</span><span class="token punctuation">(</span>target<span class="token punctuation">,</span> find<span class="token punctuation">)</span><span class="token punctuation">;</span>
target <span class="token operator">=</span> findmap<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span> <span class="token keyword">while</span> <span class="token punctuation">(</span>target<span class="token operator">++</span> <span class="token operator">&amp;&amp;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">"count is %d\n"</span><span class="token punctuation">,</span> i<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> i<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">char</span><span class="token operator">*</span> <span class="token function">subString</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> target<span class="token punctuation">,</span> <span class="token keyword">int</span> start<span class="token punctuation">,</span> <span class="token keyword">int</span> size<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">char</span><span class="token operator">*</span> result <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">char</span><span class="token operator">*</span><span class="token punctuation">)</span> <span class="token function">malloc</span> <span class="token punctuation">(</span>size<span class="token operator">*</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">strncpy</span><span class="token punctuation">(</span>result<span class="token punctuation">,</span> target <span class="token operator">+</span> start<span class="token punctuation">,</span> size<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token operator">*</span><span class="token punctuation">(</span>result<span class="token operator">+</span>size<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token string">'\0'</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">char</span><span class="token operator">*</span> <span class="token function">replaceString</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> target<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> find<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> replace<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">char</span> <span class="token operator">*</span>matchMap<span class="token punctuation">[</span><span class="token number">20</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token function">populate</span><span class="token punctuation">(</span>target<span class="token punctuation">,</span> find<span class="token punctuation">,</span> matchMap<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">"count: %d\n"</span><span class="token punctuation">,</span> count<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> sTarget <span class="token operator">=</span> <span class="token function">strlen</span><span class="token punctuation">(</span>target<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>replace<span class="token punctuation">)</span> <span class="token operator">*</span> count<span class="token punctuation">;</span> <span class="token comment">// abundantly sufficient</span>
<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">"Final size: %d\n"</span><span class="token punctuation">,</span> sTarget<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">char</span><span class="token operator">*</span> result <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">char</span><span class="token operator">*</span><span class="token punctuation">)</span> <span class="token function">malloc</span> <span class="token punctuation">(</span>sTarget <span class="token operator">*</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">char</span><span class="token operator">*</span> rp <span class="token operator">=</span> result<span class="token punctuation">;</span>
<span class="token keyword">int</span> i<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>prev <span class="token operator">=</span> target<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>index<span class="token punctuation">;</span>
<span class="token keyword">char</span> <span class="token operator">*</span>s<span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> count<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
index <span class="token operator">=</span> matchMap<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// the index where a match was found</span>
s <span class="token operator">=</span> <span class="token function">subString</span><span class="token punctuation">(</span>target<span class="token punctuation">,</span> prev <span class="token operator">-</span> target<span class="token punctuation">,</span> index <span class="token operator">-</span> prev<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">strncat</span><span class="token punctuation">(</span>rp<span class="token punctuation">,</span> prev<span class="token punctuation">,</span> index <span class="token operator">-</span> prev<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">strcat</span><span class="token punctuation">(</span>rp<span class="token punctuation">,</span> replace<span class="token punctuation">)</span><span class="token punctuation">;</span>
rp <span class="token operator">+</span><span class="token operator">=</span> <span class="token function">strlen</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>replace<span class="token punctuation">)</span><span class="token punctuation">;</span>
prev <span class="token operator">=</span> index <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>find<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">free</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token comment">// the last bit from `target` string is required</span>
s <span class="token operator">=</span> <span class="token function">subString</span><span class="token punctuation">(</span>target<span class="token punctuation">,</span> prev <span class="token operator">-</span> target<span class="token punctuation">,</span> <span class="token function">strlen</span><span class="token punctuation">(</span>target<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">strcpy</span><span class="token punctuation">(</span>rp<span class="token punctuation">,</span> s<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
<hr>
<h1 id="original-sin">Original Sin</h1>
<pre class=" language-c"><code class="prism language-c"><span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">&lt;stdio.h&gt;</span> </span>
<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">&lt;stdlib.h&gt;</span></span>
<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">&lt;string.h&gt;</span></span>
<span class="token comment">// Copyright 2014</span>
<span class="token keyword">int</span> <span class="token function">ismatchOne</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> s<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">int</span> index<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> f<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">int</span> f_i <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">return</span> f<span class="token punctuation">[</span>f_i<span class="token punctuation">]</span> <span class="token operator">==</span> s<span class="token punctuation">[</span>index <span class="token operator">+</span> f_i<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">int</span> <span class="token function">ismatch</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> target<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">int</span> index<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> find<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> f_i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> f_last <span class="token operator">=</span> <span class="token function">strlen</span><span class="token punctuation">(</span>find<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> result <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> all_match <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">while</span> <span class="token punctuation">(</span>f_i <span class="token operator">&lt;</span> f_last<span class="token punctuation">)</span><span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">ismatchOne</span> <span class="token punctuation">(</span>target<span class="token punctuation">,</span> index<span class="token punctuation">,</span> find<span class="token punctuation">,</span> f_i <span class="token punctuation">)</span><span class="token punctuation">)</span>
f_i<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token keyword">else</span> <span class="token punctuation">{</span>
all_match <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">break</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">"f_i: %d \n"</span><span class="token punctuation">,</span> f_i<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>all_match<span class="token punctuation">)</span>
result <span class="token operator">=</span> index<span class="token punctuation">;</span>
<span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">int</span> <span class="token function">populate</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> target<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> find<span class="token punctuation">,</span> <span class="token keyword">int</span> findmap<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> last <span class="token operator">=</span> <span class="token function">strlen</span><span class="token punctuation">(</span>target<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> result<span class="token punctuation">;</span>
<span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> i<span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> last<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
result <span class="token operator">=</span> <span class="token function">ismatch</span><span class="token punctuation">(</span>target<span class="token punctuation">,</span> i<span class="token punctuation">,</span> find<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>result <span class="token operator">!=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
findmap<span class="token punctuation">[</span>count<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">return</span> count<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">char</span><span class="token operator">*</span> <span class="token function">subString</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> target<span class="token punctuation">,</span> <span class="token keyword">int</span> start<span class="token punctuation">,</span> <span class="token keyword">int</span> size<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">char</span><span class="token operator">*</span> result <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">char</span><span class="token operator">*</span><span class="token punctuation">)</span> <span class="token function">malloc</span> <span class="token punctuation">(</span>size<span class="token operator">*</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> j <span class="token operator">=</span> start<span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> start <span class="token operator">+</span> size<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">,</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token operator">*</span><span class="token punctuation">(</span>result<span class="token operator">+</span>i<span class="token punctuation">)</span> <span class="token operator">=</span> target<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token operator">*</span><span class="token punctuation">(</span>result<span class="token operator">+</span>i<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token string">'\0'</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">char</span><span class="token operator">*</span> <span class="token function">replaceString</span> <span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> target<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> find<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span><span class="token operator">*</span> replace<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> matchMap<span class="token punctuation">[</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token function">populate</span><span class="token punctuation">(</span>target<span class="token punctuation">,</span> find<span class="token punctuation">,</span> matchMap<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">"count: %d\n"</span><span class="token punctuation">,</span> count<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> sTarget <span class="token operator">=</span> <span class="token function">strlen</span><span class="token punctuation">(</span>target<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>replace<span class="token punctuation">)</span> <span class="token operator">*</span> count<span class="token punctuation">;</span> <span class="token comment">// abundantly sufficient</span>
<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">"Final size: %d\n"</span><span class="token punctuation">,</span> sTarget<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">char</span><span class="token operator">*</span> result <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">char</span><span class="token operator">*</span><span class="token punctuation">)</span> <span class="token function">malloc</span> <span class="token punctuation">(</span>sTarget <span class="token operator">*</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">char</span><span class="token operator">*</span> rp <span class="token operator">=</span> result<span class="token punctuation">;</span>
<span class="token keyword">int</span> i<span class="token punctuation">;</span>
<span class="token keyword">int</span> prev <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> index<span class="token punctuation">;</span>
<span class="token keyword">char</span><span class="token operator">*</span> s<span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> count<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
index <span class="token operator">=</span> matchMap<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// the index where a match was found</span>
<span class="token comment">//printf ("i %d, index %d\n", i, index);</span>
<span class="token comment">// copy the previous bit from target, </span>
<span class="token comment">// starting at prev, and as many as 'index-prev' characters</span>
s <span class="token operator">=</span> <span class="token function">subString</span><span class="token punctuation">(</span>target<span class="token punctuation">,</span> prev<span class="token punctuation">,</span> index<span class="token operator">-</span>prev<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">//printf("prev bit from target: %s\n", s);</span>
<span class="token function">strcpy</span><span class="token punctuation">(</span>rp<span class="token punctuation">,</span> s<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">// copy the 'replace' string right after</span>
<span class="token function">strcpy</span><span class="token punctuation">(</span>rp<span class="token operator">+</span><span class="token function">strlen</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">,</span> replace<span class="token punctuation">)</span><span class="token punctuation">;</span>
rp <span class="token operator">+</span><span class="token operator">=</span> <span class="token function">strlen</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>replace<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">// push the previous beyond the "find" string</span>
prev <span class="token operator">=</span> index <span class="token operator">+</span> <span class="token function">strlen</span><span class="token punctuation">(</span>find<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">//printf ("prev %d, result: %s\n", prev, result);</span>
<span class="token function">free</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token comment">// the last bit from `target` string is required</span>
s <span class="token operator">=</span> <span class="token function">subString</span><span class="token punctuation">(</span>target<span class="token punctuation">,</span> prev<span class="token punctuation">,</span> <span class="token function">strlen</span><span class="token punctuation">(</span>target<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">strcpy</span><span class="token punctuation">(</span>rp<span class="token punctuation">,</span> s<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">// strcpy(result, target);</span>
<span class="token keyword">return</span> result<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">int</span> <span class="token function">main</span> <span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">char</span> str<span class="token punctuation">[</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> src <span class="token operator">=</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%s"</span><span class="token punctuation">,</span> str<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">char</span> find<span class="token punctuation">[</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">,</span> replace<span class="token punctuation">[</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> f <span class="token operator">=</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%s %s"</span><span class="token punctuation">,</span> find<span class="token punctuation">,</span> replace<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>src <span class="token operator">&gt;</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token operator">&amp;&amp;</span> f <span class="token operator">&gt;</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">char</span><span class="token operator">*</span> result <span class="token operator">=</span> <span class="token function">replaceString</span><span class="token punctuation">(</span>str<span class="token punctuation">,</span> find<span class="token punctuation">,</span> replace<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">"%s"</span><span class="token punctuation">,</span> result<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">else</span>
<span class="token function">printf</span> <span class="token punctuation">(</span><span class="token string">"NA"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div>
</div>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment