Pagini recente » Cod sursa (job #3120881) | Cod sursa (job #1633317) | Cod sursa (job #2499300) | Cod sursa (job #2157874) | Cod sursa (job #2738433)
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
int phi[2*NMAX+10], ans;
vector <int> poz;
int main()
{
fin >> s1 >> s2;
string s = s1 + '&' + s2;
int n1 = s1.size(), n = s.size(), i = 1, j = 0;
while(i < n)
{ if(s[i] == s[j])
{ phi[i] = j + 1;
i++;
j++;
}
else
{ if(!j)
i++;
else
j = phi[j-1];
}
}
for(int i=0; i<n; i++)
if(phi[i] == n1)
{ ans++;
if(ans <= 1000)
poz.push_back(i - 2 * n1);
}
fout << ans << '\n';
for(auto u : poz)
fout << u << ' ';
cout << '\n';
return 0;
}