Pagini recente » Cod sursa (job #8664) | Diferente pentru info-oltenia-2018/individual/7-8 intre reviziile 1 si 3 | Licență | Statistici Mihai-Catalin Stretcu (cata_s) | Cod sursa (job #631656)
Cod sursa(job #631656)
#include <fstream>
#include <vector>
using namespace std;
#define NMAX 200000
void kmp_table(char[], int[]);
int main()
{
ifstream indata;
indata.open("strmatch.in");
ofstream outdata;
outdata.open("strmatch.out");
vector <int> pozitii;
char a[NMAX], b[NMAX];
indata.getline(b, NMAX);
indata.getline(a, NMAX);
int T[strlen(b)];
kmp_table(b, T);
int m = 0, i = 0;
while (i + m < strlen(a))
if (b[i] == a[m + i])
if (i == strlen(b) - 1)
{
pozitii.push_back(m);
m += i - T[i];
i = (T[i] > -1) ? T[i] : 0;
}
else
i++;
else
{
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(char b[], int T[])
{
int pos = 2, cnd = T[1] = 0;
T[0] = -1;
while (pos < strlen(b))
if (b[pos - 1] == b[cnd])
T[pos++] = ++cnd;
else
if (cnd > 0)
cnd = T[cnd];
else
T[pos++] = 0;
}