Pagini recente » Cod sursa (job #349460) | Cod sursa (job #1802216) | Cod sursa (job #417836) | Cod sursa (job #2460035) | Cod sursa (job #1398792)
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector <int> T;
vector <int> gasite;
void kmpSearch(string s, string w)
{
int m = 0, i = 0;
int ls = s.length();
int lw = w.length();
while(m+i < ls)
{
if(w[i] == s[m+i])
{
if(i == lw-1)
{
gasite.push_back(m);
}
i++;
}
else
{
if(T[i] > -1)
{
m += i - T[i];
i = T[i];
}
else
{
i = 0;
m++;
}
}
}
}
void fillTable(string w)
{
int pos = 2;
int cnd = 0;
int lw = w.length();
T.push_back(-1);
T.push_back(0);
while(pos <= lw)
{
if(w[pos-1] == w[cnd])
{
cnd++;
T.push_back(cnd);
pos++;
}
else if(cnd > 0)
{
cnd = T[cnd];
}
else
{
T.push_back(0);
pos++;
}
}
}
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main()
{
string s1, s2;
f >> s1 >> s2;
fillTable(s1);
kmpSearch(s2, s1);
g << gasite.size() << "\n";
for(int i = 0; i < gasite.size() && i < 1000; i++)
{
//cout << i;
g << gasite[i] << " ";
}
return 0;
}