Pagini recente » Cod sursa (job #1866541) | Utilizatori inregistrati la Junior Challenge 2020 Runda 1 | Cod sursa (job #1667055) | Cod sursa (job #2676091) | Cod sursa (job #1405083)
#include <iostream>
#include <string>
using namespace std;
int t[2000000], nr, pos[1000];
string a, b;
void build_table(string word)
{
int pos = 2, cnd = 0;
t[0] = -1;
t[1] = 0;
while (pos < word.length())
{
if (word[pos - 1] == word[cnd])
{
cnd++;
t[pos] = cnd;
pos++;
}
else
if (cnd > 0)
{
cnd = t[cnd];
}
else
{
t[pos] = 0;
pos++;
}
}
}
void backtrack(int& wPos, int& mPos)
{
if (t[wPos] > -1)
{
mPos += wPos - t[wPos];
wPos = t[wPos];
}
else
{
wPos = 0;
mPos++;
}
}
void kmp_search(string word, string text)
{
int matchPos = 0, wordPos = 0;
while (matchPos + wordPos < text.length())
{
if (word[wordPos] == text[matchPos + wordPos])
{
// found a match of word in text
if (wordPos == word.length() - 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);
// string in which to find a
getline(cin, b);
build_table(a);
kmp_search(a, b);
cout << nr << "\n";
for (int i = 0; i < (nr < 1000 ? nr : 1000); i++)
{
cout << pos[i] << " ";
}
return 0;
}