Pagini recente » Statistici Budai Istvan (bisarena) | Cod sursa (job #2017240) | Cod sursa (job #673949) | Cod sursa (job #2404476) | Cod sursa (job #2006384)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
vector<int> positions;
int* getArray(string pattern)
{
int i = 1, j = 0;
int DIM = pattern.length();
int *vec = new int[DIM+1];
vec[0] = 0;
for(unsigned int i = 1; i < DIM;)
{
if(pattern[i] == pattern[j])
{
j++;
vec[i] = j;
i++;
}
else
{
if(j != 0)
j = vec[j-1];
else
{
vec[i] = 0;
i++;
}
}
}
return vec;
}
int KMP(string text,string pattern,int poz ,int *vec)
{
if(poz >= text.length())
{
return -1;
}
int j = 0,i = poz;
int position = 0;
int DIM1 = pattern.length();
int DIM2 = text.length();
while(j < DIM1 && i < DIM2)
{
if(text[i] == pattern[j])
{
i++;
j++;
}
else
{
if(j != 0)
{
j = vec[j-1];
position = i - j;
}
else
{
i++;
position = i;
}
}
}
if(j == DIM1)
{
positions.push_back(i - j);
return i-j+1;
}
return -1;
}
int main()
{
string text,pattern;
in >> pattern;
in >> text;
int *vec = getArray(pattern);
int nr = -1;
int rez = 0;
while(rez != -1)
{
nr++;
rez = KMP(text,pattern,rez,vec);
}
out << nr << '\n';
for(int i = 0; i < positions.size(); i++)
out << positions[i] << ' ';
delete[] vec;
return 0;
}