Pagini recente » Cod sursa (job #173495) | Info Oltenia 2019 Proba Individuala Clasele 5-6 | Cod sursa (job #2170210) | Istoria paginii utilizator/ionescueduard | Cod sursa (job #2588381)
#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[1001];
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 - 1 && s[i] == patt[j] && nr < 1000) ras[++nr] = i - n + 1;
}
fout << nr << "\n";
for(int i = 1; i <= nr; ++i)
fout << ras[i] << " ";
return 0;
}