Pagini recente » Cod sursa (job #3218776) | Cod sursa (job #249456) | Cod sursa (job #2516997) | Cod sursa (job #528184) | Cod sursa (job #2388355)
#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string patern, text, b = " ";
int prefix[N], potriviri;
vector <int> Sol;
int main() {
fin >> patern >> text;
int p = patern.size();
int t = text.size();
patern = b + patern;
text = b + text;
int q = 0;
for ( int i = 2 ; i <= p; i++ ) {
while ( q and patern[i] != patern[q+1] )
q = prefix[q];
if ( patern[i] == patern[q+1] )
q++;
prefix[i] = q;
}
q=0;
for ( int i = 1 ; i <= t; i++ ) {
while ( q and text[i] != patern[q+1] )
q = prefix[q];
if ( text[i] == patern[q+1] )
q++;
if ( q == p ) {
potriviri++;
if ( potriviri <= 1000 )
Sol.push_back(i-p);
}
}
fout << potriviri << "\n";
for ( auto it : Sol ) {
fout << it << " ";
}
return 0;
}