Pagini recente » Cod sursa (job #2092085) | Cod sursa (job #1141257) | Cod sursa (job #3124639) | Cod sursa (job #2750159) | Cod sursa (job #2039585)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
vector <int> v;
int pi[4000005];
char s[4000005];
void kmp (int n, int l)
{
int poz = 0;
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()
{
int n, l;
fin>>(s+1);
n = strlen (s+1);
l = n;
s[n+1] = '$';
fin>>(s+n+2);
n = strlen (s+1);
kmp (n, l);
}