Pagini recente » Cod sursa (job #403259) | Cod sursa (job #14791) | Cod sursa (job #2827047) | Cod sursa (job #3185700) | Cod sursa (job #1405175)
#include <iostream>
#include <string>
#define NMAX 2000001
using namespace std;
int t[NMAX];
unsigned int pos[1000], n, m, nr;
string a, b;
//char a[NMAX], b[NMAX];
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 backtrack(unsigned int& wPos, unsigned int& mPos)
{
if (t[wPos] > -1)
{
mPos += wPos - t[wPos];
wPos = t[wPos];
}
else
{
wPos = 0;
mPos++;
}
}
void kmp_search()
{
unsigned int matchPos = 0, wordPos = 0;
while (matchPos + wordPos < m)
{
if (a[wordPos] == b[matchPos + wordPos])
{
// found a match of word in b
if (wordPos == n - 1)
{
nr++;
if (nr <= 1000)
{
// save start position
pos[nr - 1] = matchPos;
}
backtrack(wordPos, matchPos);
}
else
{
wordPos++;
}
}
else
{
backtrack(wordPos, matchPos);
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
// word to find
getline(cin, a);
//fgets(a, sizeof(a), stdin);
//scanf("\n");
// string in which to find a
getline(cin, b);
//fgets(b, sizeof(b), stdin);
n = a.size();
/*for (int i = 0; a[i]; i++)
n++;*/
m = b.size();
/*for (int i = 0; b[i]; i++)
m++;*/
if (n > m)
{
cout << 0;
return 0;
}
else
{
if (n == m)
{
if (a == b)
{
cout << 1 << "\n" << 0;
return 0;
}
else
{
cout << 0;
return 0;
}
}
}
build_table();
kmp_search();
cout << nr << "\n";
for (int i = 0; i < (nr < 1000 ? nr : 1000); i++)
{
cout << pos[i] << " ";
}
return 0;
}