Pagini recente » Cod sursa (job #1561747) | Cod sursa (job #1470021) | Cod sursa (job #1591927) | Cod sursa (job #2489584) | Cod sursa (job #606246)
Cod sursa(job #606246)
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int N;
int occurrences[1001];
void CreateTable(const char *W, int *T, const int lenW)
{
T[0] = -1;
T[1] = 0;
/*while (pos < lenW)
{
if (W[pos-1] == W[cnd])
{
cnd++;
T[pos] = cnd;
pos++;
}
else if (cnd > 0)
{
cnd = T[cnd];
}
else
{
T[pos] = 0;
pos++;
}
}*/
int k = -1, i;
for (i = 1; i < lenW; i++)
{
while (k >= 0 && W[k + 1] != W[i])
k = T[k];
if (W[k + 1] == W[i])
k++;
T[i] = k;
}
}
inline int KMP(const char *S, const char *W, const int *T, const int lenS, const int lenW)
{
int m = 0;
int i = 0;
/*while (m+i < lenS)
{
if (S[m+i] == W[i])
{
if (i == lenW-1)
{
if (N<1000)
occurrences[N] = m;
N++;
m++;
i=0;
continue;
}
i++;
}
else
{
m = m + i - T[i];
if (T[i] > -1)
i = T[i];
else
i = 0;
}
}*/
int k = -1;
for (i = 0; i < lenS; i++)
{
while (k >= 0 && W[k + 1] != S[i])
k = T[k];
if (W[k + 1] == S[i])
k++;
if (k == lenW - 1)
{
if (N<1000)
occurrences[N++] = i - lenW + 1;
else
N++;
}
}
return lenS;
}
int main()
{
int pos = -1, oldpos = 0, lenS, lenW;
int *T;
fstream fin("strmatch.in", fstream::in);
fstream fout("strmatch.out", fstream::out);
string S;
string W;
fin >> W;
fin >> S;
fin.close();
lenS = S.length();
lenW = W.length();
//cout << W << " " << W.length() << endl;
//cout << S << " " << S.length() << endl;
T = new int[W.length()+2];
CreateTable(W.c_str(), T, W.length());
KMP(S.c_str(), W.c_str(), T, lenS, lenW);
fout << N << endl;
for (int i=0; i< ((N<=1000)?N:1000); ++i)
fout << occurrences[i] << " ";
fout << endl;
delete T;
return 0;
}