Pagini recente » Cod sursa (job #2134154) | Cod sursa (job #1835320) | Cod sursa (job #2090847) | Cod sursa (job #1776234) | Cod sursa (job #1792651)
#include <bits/stdc++.h>
#define Dim 2000010
#define Lim 1000
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);
using namespace std;
char pattern[Dim], text[Dim];
int F[Dim], lp, lt, nrsol;
vector <int> sol;
void internal_rules()
{
F[1] = 0;
int j = 0;
for (int i = 2; i <= lp; ++ i)
{
while (pattern[i] != pattern[j + 1] && j)
j = F[j];
if(pattern[i] == pattern[j + 1])
++ j;
F[i] = j;
}
}
void KMP()
{
int i, j = 0;
internal_rules();
for (i = 1; i <= lt; ++ i)
{
while (text[i] != pattern[j + 1] && j)
j = F[j];
if (text[i] == pattern[j + 1])
++ j;
if (j == lp)
{
++ nrsol;
if(nrsol <= Lim)
sol.push_back(i - lp);
}
}
}
void write()
{
printf("%d\n", nrsol);
for(int i = 0; i < sol.size(); ++ i)
printf("%d ", sol[i]);
}
int main()
{
gets(pattern + 1);
lp = strlen(pattern + 1);
gets(text + 1);
lt = strlen(text + 1);
KMP();
write();
return 0;
}