Pagini recente » Rating mihai david gavrizi (mihaigavrizi) | Cod sursa (job #2124036) | Cod sursa (job #1779685)
#include <string>
#include <fstream>
#include <vector>
using namespace std;
string a, b;
vector<int> s;
int p[2000005];
void read();
void prefix_table();
void kmp();
unsigned min(unsigned, unsigned);
void write();
int main()
{
read();
prefix_table();
kmp();
write();
return 0;
}
void read(){
ifstream fin ("strmatch.in");
fin >> a >> b;
fin.close();
}
void prefix_table(){
int j(0);
for (unsigned i = 1; i < a.size(); ++i){
while (j && a[j] != a[i])
j = p[j-1];
if (a[j] == a[i])
++j;
p[i] = j;
}
}
void kmp(){
unsigned j(0);
for (unsigned i = 0; i < b.size(); ++i){
while(j && a[j] != b[i])
j = p[j-1];
if (a[j] == b[i])
++j;
if (j == a.size())
s.push_back(i - a.size() + 1);
}
}
unsigned min(unsigned x, unsigned y){
if (x < y)
return x;
return y;
}
void write(){
ofstream fout ("strmatch.out");
fout << s.size() << "\n";
unsigned t = min(s.size(), 1000);
for (unsigned i = 0; i < t; ++i)
fout << s[i] << " ";
fout.close();
}