Pagini recente » Cod sursa (job #121554) | Cod sursa (job #1523990) | Cod sursa (job #2955814) | Cod sursa (job #2482216) | Cod sursa (job #2515589)
#include <stdio.h>
#include <string.h>
using namespace std;
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
int p,t,i,j,lps[2000005],nrap,ap[1001],k;
char patt[2000005],txt[2000005];
int main()
{ int len;
fgets(patt, 2000005, fin);
fgets(txt, 2000005, fin);
p = strlen(patt) - 1;
t = strlen(txt) - 1;
len = 0;
lps[0] = 0; // lps[0] is always 0
// the loop calculates lps[i] for i = 1 to M-1
i = 1;
while (i < p) {
if (patt[i] == patt[len]) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (len != 0) {
len = lps[len - 1];
// Also, note that we do not increment
// i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
/* for(i=1; i<=p-1; ++i)
if(patt[i] == patt[lps[i-1]])
lps[i] = lps[i-1]+1;
else
{
j = lps[i-1];
while(j>0 and patt[i] != patt[j])
j = lps[j-1];
if(j>0)
lps[i] = j+1;
else
if(patt[i] == patt[j])
lps[i] = 1;
else
lps[i] = 0;
}
*/
i = 0; // index for txt[]
j = 0; // index for pat[]
while (i < t and nrap<1000) {
if (patt[j] == txt[i]) {
j++;
i++;
}
if (j == p) {
ap[++nrap]=i-p;
j = lps[j - 1];
}
// mismatch after j matches
else if (i < t && patt[j] != txt[i]) {
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
/* i = 0; j = 0;
while(i<=t-1 and nrap<1000)
{
while(i<=t-1 and j<=p-1 and patt[j] == txt[i])
{ ++i; ++j;}
if(j > p-1)
{
ap[++nrap] = i-p;
j = lps[p-1];
continue;
}
if(i>t-1)
break;
if(j == 0)
++i;
else
{
k = lps[j-1];
while(k>0 and patt[k]!=txt[i])
k = lps[k-1];
if(k>0)
j = k;
else
if(k==0 and patt[0]==txt[i])
j = 0;
else
{
++i;
j = 0;
}
}
}
*/
fprintf(fout, "%d\n", nrap);
for(i=1; i<=nrap; ++i)
fprintf(fout, "%d ", ap[i]);
fclose(fin);
fclose(fout);
return 0;
}