Pagini recente » Cod sursa (job #2416579) | Cod sursa (job #1779157) | Cod sursa (job #2395729) | Cod sursa (job #2581957) | Cod sursa (job #670581)
Cod sursa(job #670581)
#include<fstream>
#include<iostream>
#include<vector>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
vector<int> matches;
string sir, subsir;
int pi[2000000+10];
int main()
{
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
getline(fin, subsir);
getline(fin, sir );
// subsir.insert(subsir.begin(),'-');//incepem de la 1, nu de la 0 //TODO
// sir.insert(sir.begin(),'-'); //incepem de la 1, nu de la 0 //TODO
if (sir.size()<subsir.size()) {
fout<<0<<'\n';
return 0;
}
int k=0;
pi[1]=0;
for(int i=1; i<subsir.length(); ++i) {
while(k>0 && subsir[i] != subsir[k])
k=pi[k];
if(subsir[i] == subsir[k])
k++;
pi[i+1]=k;
}
k=0;
int nr=0;
for(int i=0; i<sir.length(); ++i) {
while(k>0 && sir[i] != subsir[k])
k=pi[k];
if(sir[i] == subsir[k])
k++;
if(k==subsir.length()) { //match
if(matches.size()<1000) {
matches.push_back(i-subsir.length()+1);
}
nr++;
}
}
fout<<nr<<'\n';
for(int i=0; i<matches.size(); ++i) {
fout<<matches[i]<<' ';
}
fout<<'\n';
fout.close();
return 0;
}