Pagini recente » Cod sursa (job #238864) | Cod sursa (job #2623869) | Cod sursa (job #1512880) | Cod sursa (job #3226588) | Cod sursa (job #1971315)
#include <bits/stdc++.h>
using namespace std;
int Pi[4000005];
char s[4000005];
int poz = 0;
vector <int> v;
ofstream fout ("strmatch.out");
void KMP (int n, int l)
{
for (int i = 2; i<=n; ++i)
{
Pi[i] = Pi[i-1];
while (Pi[i] && s[i]!=s[Pi[i]+1]) Pi[i] = Pi[Pi[i]];
if (s[i] == s[Pi[i]+1]) ++Pi[i];
if (Pi[i] == l)
{
++poz;
if (poz<=1000)
v.push_back(i-l-l-1);
}
}
fout << poz << '\n';
for (auto x:v)
fout << x << " ";
}
int main()
{
ifstream fin ("strmatch.in");
fin >> (s+1);
int n = strlen(s+1), l;
l = n;
s[n+1] = '%';
fin >> (s+n+2);
n = strlen(s+1);
KMP(n, l);
return 0;
}