Pagini recente » Cod sursa (job #2588513) | Cod sursa (job #1335742) | Cod sursa (job #2176156) | Cod sursa (job #1598171) | Cod sursa (job #2713860)
#include <bits/stdc++.h>
using namespace std;
const string FILENAME = "strmatch";
ifstream fin(FILENAME + ".in");
ofstream fout(FILENAME + ".out");
string pat, txt;
vector<int> ans;
int lps[2000001];
void computeLps(string pat, int m)
{
int len = 0;
lps[0] = 0;
int i = 1;
while(i < m)
{
if(pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if(len != 0)
len = lps[len - 1];
else
{
lps[i] = 0;
i++;
}
}
}
}
void KMPSearch(string pat, string txt)
{
int n = txt.size(), m = pat.size();
computeLps(pat, m);
int i = 0, j = 0;
while(i < n)
{
if(pat[j] == txt[i])
{
i++;
j++;
}
if(j == m)
{
ans.push_back(i - j);
j = lps[j - 1];
}
else if(i < n && pat[j] != txt[i])
{
if(j != 0) j = lps[j - 1];
else i++;
}
}
}
int main()
{
fin >> pat >> txt;
KMPSearch(pat, txt);
fout << ans.size() << "\n";
for(auto i : ans)
fout << i << " ";
fin.close();
fout.close();
return 0;
}