Pagini recente » Istoria paginii runda/preoji2020/clasament | Cod sursa (job #2671074) | Cod sursa (job #1195201) | Cod sursa (job #189500) | Cod sursa (job #2445021)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int DIM = 2e6;
int N, M;
char a[DIM + 5], b[DIM + 5];
int pi[DIM + 5];
int ans;
vector <int> kmp;
void Pi()
{
int j = 0;
for(int i = 2; i <= N; i++) {
while(a[i] != a[j + 1] && j != 0)
j = pi[j];
if(a[i] == a[j + 1])
j++;
pi[i] = j;
}
}
void Kmp()
{
int j = 0;
for(int i = 1; i <= M; i++) {
while(b[i] != a[j + 1] && j != 0)
j = pi[j];
if(b[i] == a[j + 1])
j++;
if(j == N) {
ans++;
if(kmp.size() <= 1000)
kmp.push_back(i - N);
j = pi[j];
}
}
}
int main()
{
fin >> (a + 1); N = strlen(a + 1);
fin >> (b + 1); M = strlen(b + 1);
Pi();
Kmp();
fout << ans << '\n';
for(auto it : kmp)
fout << it << ' ';
return 0;
}