Pagini recente » Statistici Sorean Gabriel Alin (demonliver) | Cod sursa (job #744049) | Cod sursa (job #536372) | Cod sursa (job #1325448) | Cod sursa (job #2415501)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000000;
int N, M;
char a[NMAX + 5], b[NMAX + 5];
int pi[NMAX + 5];
int ans;
vector <int> sol;
void Pi()
{
int j = 0;
for(int i = 2; i <= N; i++)
{
while(j != 0 && a[j + 1] != a[i])
j = pi[j];
if(a[j + 1] == a[i])
j++;
pi[i] = j;
}
}
void Kmp()
{
int j = 0;
for(int i = 1; i <= M; i++)
{
while(j != 0 && a[j + 1] != b[i])
j = pi[j];
if(a[j + 1] == b[i])
j++;
if(j == N)
{
ans++;
if(ans <= 1000)
sol.push_back(i - N);
j = pi[j];
}
}
fout << ans << '\n';
for(auto it : sol)
fout << it << ' ';
}
int main()
{
fin >> (a + 1) >> (b + 1);
N = strlen(a + 1);
M = strlen(b + 1);
Pi();
Kmp();
return 0;
}