Pagini recente » Cod sursa (job #2826729) | Cod sursa (job #951612) | Cod sursa (job #552561) | Cod sursa (job #1526253) | Cod sursa (job #2305507)
#include <fstream>
#include <cstring>
#define LungimeMaxima 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char pattern[LungimeMaxima];
char text[LungimeMaxima];
char lps[LungimeMaxima];
int nr;
int potrivire[100000];
void CreareLps(int Lungime)
{
int i = 1;
int len = 0;
lps[0] = 0;
while (i < Lungime)
{
if (pattern[i] == pattern[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len == 0)
{
lps[i] = 0;
i++;
}
else len = lps[len - 1];
}
}
}
void KMP()
{
int i = 0;
int j = 0;
int n = strlen(text);
int m = strlen(pattern);
CreareLps(m);
while (i < n )
{
if (pattern[j] == text[i])
{
i++;
j++;
}
if (j == m)
{
nr++;
potrivire[nr] = i - j;
j = lps[j-1];
}
else if (i < n && pattern[j] != text[i])
{
if (j == 0)
{
i++;
}
else j = lps[j - 1];
}
}
}
void afisare()
{
fout << nr << "\n";
for (int i = 1; i <= nr; i++)
fout << potrivire[i] << " ";
}
int main()
{
fin.getline(pattern,LungimeMaxima-1);
fin.getline(text,LungimeMaxima-1);
KMP();
afisare();
return 0;
}