Pagini recente » Cod sursa (job #3168153) | Cod sursa (job #2179637) | Cod sursa (job #1668371) | Cod sursa (job #722515) | Cod sursa (job #3169263)
#include <fstream>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NMAX = 4000000;
int pi[NMAX + 5];
int main()
{
string s1, s2;
fin >> s1 >> s2;
s2 = "$" + s1 + "$" + s2;
int l1 = s1.size(), l2 = s2.size();
for(int i = 2; i < l2; i++)
{
int k = pi[i - 1];
while(s2[i] != s2[k + 1] && k)
k = pi[k];
if(s2[i] == s2[k + 1])
k++;
pi[i] = k;
}
int cnt = 0;
for(int i = 0; i < l2; i++)
if(pi[i] == l1)
cnt++;
fout << cnt << '\n';
int cnt1 = 0;
for(int i = 0; i < l2; i++)
{
if(cnt1 == 1000)
break;
if(pi[i] == l1)
{
cnt1++;
fout << i - 2 * l1 - 1 << ' ';
}
}
fin.close();
fout.close();
return 0;
}