Pagini recente » Cod sursa (job #918011) | Cod sursa (job #43991) | Cod sursa (job #2121371) | Cod sursa (job #2468715) | Cod sursa (job #3168535)
#include <fstream>
#include <cstring>
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 len2 = s2.size(), len1 = s1.size();
for(int i = 2; i < len2; i++)
{
int k = pi[i - 1];
while(s2[i] != s2[k + 1] && k != 0)
k = pi[k];
if(s2[i] == s2[k + 1])
k++;
pi[i] = k;
}
int cnt = 0;
for(int i = 0; i < len2; i++)
if(pi[i] == len1)
cnt++;
fout << cnt << '\n';
int cnt1 = 0;
for(int i = 0; i < len2; i++)
{
if(cnt1 == 1000)
break;
if(pi[i] == len1)
{
cnt1++;
fout << i - 2 * len1 - 1 << ' ';
}
}
fin.close();
fout.close();
return 0;
}