Pagini recente » Cod sursa (job #3359965) | Cod sursa (job #3359963) | Cod sursa (job #3359972) | Cod sursa (job #3359976) | Cod sursa (job #3359971)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int main() {
string a,b;
cin>>a>>b;
int n=a.length();
int m=b.length();
vector<int> pi(n,0);
int j=0;
for (int i=1; i<n; ++i) {
while (j>0 && a[i]!=a[j]) {
j=pi[j-1];
}
if (a[i]==a[j]) {
j++;
}
pi[i]=j;
}
vector<int> matches;
j=0;
for (int i=0; i<m; ++i) {
while (j>0 && b[i]!=a[j]) {
j=pi[j-1];
}
if (b[i]==a[j]) {
j++;
}
if (j==n) {
matches.push_back(i-n+1);
j=pi[n-1];
}
}
cout<<matches.size()<<"\n";
int limit=matches.size();
if (limit>1000) {
limit=1000;
}
for (int i=0; i<limit; ++i) {
cout<<matches[i]<<(i==limit-1?"":" ");
}
cout<<"\n";
}