Pagini recente » Cod sursa (job #2918128) | Cod sursa (job #149627) | Cod sursa (job #2869073) | Cod sursa (job #1385877) | Cod sursa (job #917536)
Cod sursa(job #917536)
<HTML><META HTTP-EQUIV="content-type" CONTENT="text/html;charset=utf-8">
<p class="container"><p class="line number1 index0 alt2"><CODE class="cpp preprocessor">#include<cstdio></CODE></DIV><p class="line number2 index1 alt1"><CODE class="cpp preprocessor">#include<cstring></CODE></DIV><p class="line number3 index2 alt2"><CODE class="cpp color1 bold">int</CODE> <CODE class="cpp plain">n,m,i,k,nr,v[2000005],w[2000005];</CODE></DIV><p class="line number4 index3 alt1"><CODE class="cpp color1 bold">char</CODE> <CODE class="cpp plain">s[2000005],t[2000005];</CODE></DIV><p class="line number5 index4 alt2"> </DIV><p class="line number6 index5 alt1"> </DIV><p class="line number7 index6 alt2"><CODE class="cpp keyword bold">void</CODE> <CODE class="cpp plain">citire()</CODE></DIV><p class="line number8 index7 alt1"><CODE class="cpp plain">{</CODE></DIV><p class="line number9 index8 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp functions bold">freopen</CODE><CODE class="cpp plain">(</CODE><CODE class="cpp string">"strmatch.in"</CODE><CODE class="cpp plain">,</CODE><CODE class="cpp string">"r"</CODE><CODE class="cpp plain">,stdin);</CODE></DIV><p class="line number10 index9 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp functions bold">freopen</CODE><CODE class="cpp plain">(</CODE><CODE class="cpp string">"strmatch.out"</CODE><CODE class="cpp plain">,</CODE><CODE class="cpp string">"w"</CODE><CODE class="cpp plain">,stdout);</CODE></DIV><p class="line number11 index10 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp functions bold">gets</CODE><CODE class="cpp plain">(s+1);</CODE></DIV><p class="line number12 index11 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp functions bold">gets</CODE><CODE class="cpp plain">(t+1);</CODE></DIV><p class="line number13 index12 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">n=</CODE><CODE class="cpp functions bold">strlen</CODE><CODE class="cpp plain">(s+1);</CODE></DIV><p class="line number14 index13 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">m=</CODE><CODE class="cpp functions bold">strlen</CODE><CODE class="cpp plain">(t+1);</CODE></DIV><p class="line number15 index14 alt2"><CODE class="cpp plain">}</CODE></DIV><p class="line number16 index15 alt1"> </DIV><p class="line number17 index16 alt2"><CODE class="cpp keyword bold">void</CODE> <CODE class="cpp plain">prefix()</CODE></DIV><p class="line number18 index17 alt1"><CODE class="cpp plain">{</CODE></DIV><p class="line number19 index18 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">k=0;</CODE></DIV><p class="line number20 index19 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp keyword bold">for</CODE><CODE class="cpp plain">(i=2;i<=n;i++){</CODE></DIV><p class="line number21 index20 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp keyword bold">while</CODE><CODE class="cpp plain">(k>0 && s[k+1]!=s[i])k=v[k];</CODE></DIV><p class="line number22 index21 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp keyword bold">if</CODE><CODE class="cpp plain">(s[k+1]==s[i])k++;</CODE></DIV><p class="line number23 index22 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">v[i]=k;</CODE></DIV><p class="line number24 index23 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">}</CODE></DIV><p class="line number25 index24 alt2"><CODE class="cpp plain">}</CODE></DIV><p class="line number26 index25 alt1"> </DIV><p class="line number27 index26 alt2"><CODE class="cpp keyword bold">void</CODE> <CODE class="cpp plain">kmp()</CODE></DIV><p class="line number28 index27 alt1"><CODE class="cpp plain">{</CODE></DIV><p class="line number29 index28 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">k=0;</CODE></DIV><p class="line number30 index29 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp keyword bold">for</CODE><CODE class="cpp plain">(i=1;i<=m;i++){</CODE></DIV><p class="line number31 index30 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp keyword bold">while</CODE><CODE class="cpp plain">(k>0 && s[k+1]!=t[i])k=v[k];</CODE></DIV><p class="line number32 index31 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp keyword bold">if</CODE><CODE class="cpp plain">(s[k+1]==t[i])k++;</CODE></DIV><p class="line number33 index32 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp keyword bold">if</CODE><CODE class="cpp plain">(k==n){</CODE></DIV><p class="line number34 index33 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">nr++;</CODE></DIV><p class="line number35 index34 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">w[nr]=i-n;</CODE></DIV><p class="line number36 index35 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">k=v[k];</CODE></DIV><p class="line number37 index36 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">}</CODE></DIV><p class="line number38 index37 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">}</CODE></DIV><p class="line number39 index38 alt2"><CODE class="cpp spaces"> </CODE> </DIV><p class="line number40 index39 alt1"><CODE class="cpp plain">}</CODE></DIV><p class="line number41 index40 alt2"> </DIV><p class="line number42 index41 alt1"><CODE class="cpp keyword bold">void</CODE> <CODE class="cpp plain">afisare()</CODE></DIV><p class="line number43 index42 alt2"><CODE class="cpp plain">{</CODE></DIV><p class="line number44 index43 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp functions bold">printf</CODE><CODE class="cpp plain">(</CODE><CODE class="cpp string">"%d\n"</CODE><CODE class="cpp plain">,nr);</CODE></DIV><p class="line number45 index44 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp keyword bold">if</CODE><CODE class="cpp plain">(nr>1000)nr=1000;</CODE></DIV><p class="line number46 index45 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp keyword bold">for</CODE><CODE class="cpp plain">(i=1;i<=nr;i++)</CODE><CODE class="cpp functions bold">printf</CODE><CODE class="cpp plain">(</CODE><CODE class="cpp string">"%d "</CODE><CODE class="cpp plain">,w[i]);</CODE></DIV><p class="line number47 index46 alt2"><CODE class="cpp spaces"> </CODE> </DIV><p class="line number48 index47 alt1"><CODE class="cpp plain">}</CODE></DIV><p class="line number49 index48 alt2"> </DIV><p class="line number50 index49 alt1"><CODE class="cpp color1 bold">int</CODE> <CODE class="cpp plain">main()</CODE></DIV><p class="line number51 index50 alt2"><CODE class="cpp plain">{</CODE></DIV><p class="line number52 index51 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">citire();</CODE></DIV><p class="line number53 index52 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">prefix();</CODE></DIV><p class="line number54 index53 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">kmp();</CODE></DIV><p class="line number55 index54 alt2"><CODE class="cpp spaces"> </CODE><CODE class="cpp plain">afisare();</CODE></DIV><p class="line number56 index55 alt1"><CODE class="cpp spaces"> </CODE><CODE class="cpp keyword bold">return</CODE> <CODE class="cpp plain">0;</CODE></DIV><p class="line number57 index56 alt2"><CODE class="cpp plain">}</CODE></DIV></DIV>
Apopeid Alejandro apopeid13