Pagini recente » Cod sursa (job #2553994) | Istoria paginii runda/148/clasament | Cod sursa (job #655008) | Cod sursa (job #2137634) | Cod sursa (job #2588429)
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define INF 1234567890
#define N (int)(2e6 + 5)
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int ps[N];
vector <int> ras;
int main()
{
string patt, s;
fin >> patt >> s;
int nr = 0;
int n = patt.length(), m = s.length();
int i = 0, j = 1;
while(j < n)
{
if(patt[i] == patt[j]) ps[j] = i + 1, i++, j++;else
if(!i) ++j;else i = ps[i - 1];
}
i = 0, j = 0;
while(i < m)
{
if(s[i] == patt[j]) i++, j++;else
if(!j) ++i;else j = ps[j - 1];
if(j == n && s[i - 1] == patt[j - 1])
ras.push_back(i - n), j = ps[j - 1];
}
nr = ras.size();
fout << nr << "\n";
for(int i = 0; i < nr; ++i)
fout << ras[i] << " ";
return 0;
}