Pagini recente » Cod sursa (job #897065) | Cod sursa (job #3183775) | Cod sursa (job #964366) | Cod sursa (job #456953) | Cod sursa (job #1405210)
#include <fstream>
#include <string>
#define NMAX 2000001
using namespace std;
int t[NMAX];
unsigned int pos[1000], n, m, nr;
string a, b;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void build_table()
{
unsigned int wPos = 2, cnd = 0;
t[0] = -1;
t[1] = 0;
while (wPos < n)
{
if (a[wPos - 1] == a[cnd])
{
cnd++;
t[wPos] = cnd;
wPos++;
}
else
if (cnd > 0)
{
cnd = t[cnd];
}
else
{
t[wPos] = 0;
wPos++;
}
}
}
void kmp_search()
{
unsigned int matchPos = 0, wordPos = 0;
while (matchPos + wordPos < m)
{
bool backtrack = true;
if (a[wordPos] == b[matchPos + wordPos])
{
backtrack = false;
// found a match of word in b
if (wordPos == n - 1)
{
nr++;
if (nr <= 1000)
{
// save start position
pos[nr - 1] = matchPos;
}
backtrack = true;
}
else
{
wordPos++;
}
}
if (backtrack)
{
if (t[wordPos] > -1)
{
matchPos += wordPos - t[wordPos];
wordPos = t[wordPos];
}
else
{
wordPos = 0;
matchPos++;
}
}
}
}
int main()
{
// word to find
getline(f, a);
// string in which to find a
getline(f, b);
n = a.size();
m = b.size();
if (m == n)
{
if (a == b)
{
g << 1 << "\n" << 0;
}
else
{
g << 0;
}
return 0;
}
build_table();
kmp_search();
g << nr << "\n";
for (int i = 0; i < (nr < 1000 ? nr : 1000); i++)
{
g << pos[i] << " ";
}
return 0;
}