Pagini recente » Cod sursa (job #961468) | Cod sursa (job #1225995) | Cod sursa (job #227796) | Cod sursa (job #1247684) | Cod sursa (job #1153128)
#include<fstream>
#include<string>
#include<queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p, t;
int m, i, k, v[2000000], n, j;
queue <int> q;
int main(){
getline(fin, p);
getline(fin, t);
p.insert(0, " ");
t.insert(0, " ");
n = t.length() - 1;
m = p.length() - 1;
for (i = 2; i <= m; i++){
while (k > 0 and p[k + 1] != p[i])
k = v[k];
if (p[k + 1] == p[i]){
k++;
v[i] = k;
}
}
// for (i = 1; i <= m; i++)
// fout << v[i] << " ";
i = 0; j = 1;
while (j <= n){
if (p[i + 1] == t[j]){
i++;
j++;
if (i == m)
q.push(j - i - 1);//fout << j - i << " ";
}
else if (i > 0)
i = v[i];
else
j++;
}
fout << q.size() << '\n';
i = 1;
while (!q.empty() and i <= 1000){
fout << q.front() << " "; i++;
q.pop();
}
fin.close();
fout.close();
}