Pagini recente » Cod sursa (job #167651) | Cod sursa (job #1945493) | Istoria paginii runda/oni-2018-10-ziua2 | Cod sursa (job #2553988) | Cod sursa (job #2588402)
#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];
int ras[3001];
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] && nr < 2000)
ras[++nr] = i - n, j = ps[j - 1];
}
fout << nr << "\n";
for(int i = 1; i <= min(1000, nr); ++i)
fout << ras[i] << " ";
return 0;
}