Pagini recente » Cod sursa (job #1891997) | Cod sursa (job #2775083) | Cod sursa (job #244878) | Cod sursa (job #261249) | Cod sursa (job #631652)
Cod sursa(job #631652)
#include <fstream>
#include <vector>
using namespace std;
#define NMAX 2000
int T[NMAX];
char a[NMAX], b[NMAX];
void kmp_table();
int main()
{
ifstream indata;
indata.open("strmatch.in");
ofstream outdata;
outdata.open("strmatch.out");
vector <int> pozitii;
int m = 0, i = 0;
indata.getline(b, NMAX);
indata.getline(a, NMAX);
kmp_table();
while (i + m < strlen(a))
{
if (b[i] == a[m + i])
{
if (i == strlen(b) - 1)
{
pozitii.push_back(m);
m = m + i - T[i];
i = (T[i] > -1) ? T[i] : 0;
}
else
i++;
}
else
{
m = m + i - T[i];
i = (T[i] > -1) ? T[i] : 0;
}
}
outdata<<pozitii.size()<<"\n";
for (int i = 0; i < pozitii.size(); i++)
outdata<<pozitii[i]<<" ";
}
void kmp_table()
{
int pos = 2, cnd = 0;
T[0] = -1;
T[1] = 0;
while (pos < strlen(b))
if (b[pos - 1] == b[cnd])
{
cnd++;
T[pos] = cnd;
pos++;
}
else
if (cnd > 0)
cnd = T[cnd];
else
{
T[pos] = 0;
pos++;
}
}