Pagini recente » Cod sursa (job #2387157) | Cod sursa (job #2397033) | Cod sursa (job #2573747) | Cod sursa (job #642282) | Cod sursa (job #2433677)
#include <cstring>
#include <fstream>
#define maxn 2000005
std :: ifstream cin("strmatch.in");
std :: ofstream cout("strmatch.out");
void computeLPSArray(char* pat, int M, int* lps);
int rasp[maxn], nr;
void KMPSearch(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
int lps[M];
computeLPSArray(pat, M, lps);
int i = 0;
int j = 0;
while (i < N)
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
rasp[++nr] = i - j ;
j = lps[j - 1];
}
else if (i < N && pat[j] != txt[i])
{
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
void computeLPSArray(char* pat, int M, int* lps)
{
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0)
{
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
char pat[maxn], txt[maxn];
int main()
{
cin >> pat >> txt;
KMPSearch(pat, txt);
cout << nr << '\n';
(nr > 1000) ? nr = 1000 : nr = nr;
for(int i = 1; i <= nr; i++)
cout << rasp[i] << ' ';
return 0;
}