Pagini recente » Cod sursa (job #2905171) | Cod sursa (job #166756) | Cod sursa (job #2673522) | Cod sursa (job #1912265) | Cod sursa (job #3262747)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
const int NMAX = 2000001;
int prefix[NMAX];
void calculatePrefix (const string& pat)
{
int lg = 0, n = pat.size();
prefix[0] = 0;
for (int i = 1; i < n; i++)
{
while (pat[i] != pat[lg] && lg != 0)
lg = prefix[lg - 1];
if (pat[i] == pat[lg])
lg++;
prefix[i] = lg;
}
}
int getOccurences (string &pat, string& txt, vector<int> &ans)
{
int cnt = 0, m = txt.size(), n = pat.size();
int lg = 0;
for (int i = 0; i < m; i++)
{
if (pat[lg] == txt[i])
{
lg++;
}
else
{
while (txt[i] != pat[lg] && lg != 0)
lg = prefix[lg - 1];
if (txt[i] == pat[lg])
lg++;
}
if (lg == n)
{
cnt ++;
if (cnt <= 1000)
ans.push_back (i - lg + 1);
lg = prefix[lg - 1];
}
}
return cnt;
}
int main()
{
string txt, pat;
f >> pat >> txt;
calculatePrefix (pat);
vector<int>ans;
g << getOccurences (pat, txt, ans) << '\n';
for (auto pos : ans)
{
g << pos << ' ';
}
return 0;
}