Pagini recente » Cod sursa (job #329066) | Cod sursa (job #1411544) | Cod sursa (job #1361091) | Cod sursa (job #272684) | Cod sursa (job #2006387)
#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 j = 0;
int DIM = pattern.length();
int *vec = new int[DIM+1];
vec[0] = 0;
for(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 main()
{
string text,pattern;
in >> pattern;
in >> text;
int *vec = getArray(pattern);
int nr = 0;
int DIM1 = pattern.length();
int DIM2 = text.length();
int i =0;int j = 0;
while(i < DIM2 )
{
if(text[i] == pattern[j])
{
i++;
j++;
}
else
{
if(j != 0)
{
j = vec[j-1];
}
else
{
i++;
}
}
if(j == DIM1)
{
positions.push_back(i - j);
i=i-j+1;
nr++;
j = 0;
}
}
out << nr << '\n';
int DIM = positions.size();
if(DIM > 1000)
DIM = 1000;
for( int i = 0; i < DIM ; i++)
out << positions[i] << ' ';
delete[] vec;
return 0;
}